Hi,
if you know the Python internals, here is a newbie question for you.
If I have a list with 100 elements, each element being a long string,
is it more efficient to maintain it as a dictionary (with a key = a
string from the list and value = None) for the purpose of insertion
and removal?
Basically, if Python really implements lists as linked lists but
dictionaries as hash tables, it may well be that hashing a key takes
negligible time as compared to comparing it against every list
element.
Oh and here is (as a non-sequiter) something I don't understand
either: x = ([],) x[0] += ['something']
Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: object doesn't support item assignment x
(['something'],) <---- complained but did it anyway?? x[0].append('and another thing') <------- no complaint! x
(['something', 'and another thing'],) 6 2657
Narendra C. Tulpule wrote: If I have a list with 100 elements, each element being a long string, is it more efficient to maintain it as a dictionary (with a key = a string from the list and value = None) for the purpose of insertion and removal?
Wild guess: I suppose that both implementations will not significantly
affect the overall speed of your application, e.g. if the strings are
*really* large (as opposed to the list of *only* 100 elements), reading
from disk will take much longer than inserting into the list, even at
arbitrary positions.
Also, note that no particular order is preserved for the keys in a
dictionary.
And now for something completely different: x = ([],) x[0] += ['something'] Traceback (most recent call last): File "<stdin>", line 1, in ? TypeError: object doesn't support item assignment
+= calls the list.__iadd__(s elf, other) method, which seems to be
implemented as
def __iadd__(self, other):
self.append(oth er)
return self
The call of this method succeds, but the following assignment fails, because
tuples are immutable. This could only be remedied if all assignments
a = a
were silently ignored, or, if the += operator would not perform an
assignment, which has the disadvantage that it would no longer work for
immutables, so that i = 1 i += 1 print i
1 # admittedly faked
You could change __iadd__() to
def __iadd__(self, other):
return self + other
but then sane behaviour in one special case comes at the cost of always
creating a copy of a potentially large (say more than 100 items :-) list.
By the way, one topic per post is always a good idea :-)
Peter
Narendra C. Tulpule wrote: Hi, if you know the Python internals, here is a newbie question for you. If I have a list with 100 elements, each element being a long string, is it more efficient to maintain it as a dictionary (with a key = a string from the list and value = None) for the purpose of insertion and removal?
If you use a dictionary, there will be no "intrinsic" ordering -- you
may as well use sets, then. "Insertion" for a list would thus just
be an .append, very fast. "removal" may be O(N) for a list, if you
need to search through it for occurrences.
Basically, if Python really implements lists as linked lists but dictionaries as hash tables, it may well be that hashing a key takes negligible time as compared to comparing it against every list element.
Python's lists are actually vectors, dicts are indeed hash tables.
Hashing a long string does take some time, but the value may be
cached (depending on the Python implementation) so that said time
need be spent only once for a given string object (but separate
string objects will spend the time multiply, even if it so happens
that their values coincide).
All in all, there's no serious alternative to benchmarking both
possibilities in a realistic scenario. Quite likely you may find
out that -- for sensible frequencies of insertiom / removal --
the time doesn't matter for your application overall (dominated
by I/O or other issues), and then you can use the simplest rather
than the fastest approach. At least 9 times out of 10 you will
be happiest with simplicity. If you don't care about ordering,
Python 2.3's sets are likely the simplest data structure (they
are implemented in terms of dictionaries, thus pretty fast too).
Alex
On Fri, Aug 29, 2003 at 10:07:20AM +0200, Peter Otten wrote: Narendra C. Tulpule wrote:
[ snip] And now for something completely different:
> x = ([],) > x[0] += ['something'] Traceback (most recent call last): File "<stdin>", line 1, in ? TypeError: object doesn't support item assignment
+= calls the list.__iadd__(s elf, other) method, which seems to be implemented as
def __iadd__(self, other): self.append(oth er) return self
self.extend(oth er), actually. But that's the basic idea, yea. The call of this method succeds, but the following assignment fails, because tuples are immutable. This could only be remedied if all assignments
a = a
were silently ignored, or, if the += operator would not perform an assignment, which has the disadvantage that it would no longer work for immutables, so that i = 1 i += 1 print i 1 # admittedly faked
+= could simply be syntactic sugar for a call to __add__ and then an
assignment. This would work for mutable and immutable objects. You could change __iadd__() to
def __iadd__(self, other): return self + other
but then sane behaviour in one special case comes at the cost of always creating a copy of a potentially large (say more than 100 items :-) list.
True, except that list.extend() exists.
Jp
--
"There is no reason for any individual to have a computer in their
home."
-- Ken Olson, President of DEC, World Future Society
Convention, 1977
"Narendra C. Tulpule" <na***@trillium .com> wrote in message
news:78******** *************** ***@posting.goo gle.com... Hi, if you know the Python internals, here is a newbie question for you. If I have a list with 100 elements, each element being a long string, is it more efficient to maintain it as a dictionary (with a key = a string from the list and value = None) for the purpose of insertion and removal?
Lists are more efficient for lookup by index, dictionaries are
more efficient for insertion (except at the end, where Python
maintains extra slots for just this case), removal and lookup
by key. Lists are also much more efficient for sequential
traversal.
John Roth
On Fri, Aug 29, 2003 at 10:24:37AM -0700, Chad Netzer wrote: On Fri, 2003-08-29 at 07:54, Jp Calderone wrote:
+= could simply be syntactic sugar for a call to __add__ and then an assignment. This would work for mutable and immutable objects.
But it loses the advantage that some objects would otherwise have of being able to mutate in place, without allocating a new object (ie. very large matrix additions).
But as you removed from my original post, list.extend() exists. All one
has to do to retain the existing functionality of __iadd__ is name the
method something else, then call it. All the advantages, none of the
confusing or difficult to track semantics.
Jp
On Sat, 2003-08-30 at 00:03, Jp Calderone wrote: But as you removed from my original post, list.extend() exists. All one has to do to retain the existing functionality of __iadd__ is name the method something else, then call it. All the advantages, none of the confusing or difficult to track semantics.
True, however when working with large Matrices, I much prefer A += B, to
A.add(B), and the performance advantages with __iadd__ can be
substantial.
I prefer the original posters suggestion that self assignment be
ignored. But I see your point about the more difficult semantics of
__iadd__.
--
Chad Netzer This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Nickolay Kolev |
last post by:
Hi all,
Continuing the search for interesting challenges with lists, tuples and
dictionaries I am looking for a way to do the following.
one = {
'a' : 1,
'b' : 2,
'c' : 3
}
|
by: David Pratt |
last post by:
Hi. I like working with lists of dictionaries since order is preserved
in a list when I want order and the dictionaries make it explicit what
I have got inside them. I find this combination very useful for storing
constants especially. Generally I find myself either needing to
retrieve the values of constants in an iterative way (as in my
contrived example below). Perhaps even more frequent is given one value
is to look up the matching...
|
by: François Pinard |
last post by:
Hi, people.
I noticed today that dictionaries seem to support `==' comparison.
(Retrospectively, it is strange that I never needed it before! :-)
Yet, before relying on this, I seeked for confirmation in the Python
manuals, and did not succeed in finding it. In particular:
http://www.python.org/doc/2.3.5/lib/typesmapping.html
is silent on the subject. As for:
|
by: Brian Cole |
last post by:
I need to iterate through a file, checking whether each line
'startswith()' a string that belongs to a set.
Normally, the most efficient way I would do this would be:
strs=set()
for line in file:
if line.strip() in strs:
print line
However, for this case I need to do a startswith like this:
|
by: SMB |
last post by:
I have two lists of data like the following:
LIST1
, ]
LIST2
, 'label': 'First Name',
'width': 0L, 'separator': ',', 'height': 0L, 'type': 2L, 'order': 1L},
{'code': 14L, 'name': 'Last Name', 'value': , 'label': 'Last Name',
'width': 0L, 'separator': ',', 'height': 0L, 'type': 2L, 'order': 2L},
| |
by: lysdexia |
last post by:
I'm having great fun playing with Markov chains. I am making a
dictionary of all the words in a given string, getting a count of how
many appearances word1 makes in the string, getting a list of all the
word2s that follow each appearance of word1 and a count of how many
times word2 appears in the string as well. (I know I should probably
be only counting how many times word2 actually follows word1, but as I
said, I'm having great fun...
|
by: Tem |
last post by:
List<inta = new List<int>();
a.Add(1);
a.Add(2);
a.Add(3);
List<intb = new List<int>();
b.Add(3);
b.Add(4);
b.Add(5);
|
by: Brandon |
last post by:
Hi all,
I am not altogether experienced in Python, but I haven't been able to
find a good example of the syntax that I'm looking for in any tutorial
that I've seen. Hope somebody can point me in the right direction.
This should be pretty simple: I have two dictionaries, foo and bar.
I am certain that all keys in bar belong to foo as well, but I also
know that not all keys in foo exist in bar. All the keys in both foo
and bar are...
|
by: cnb |
last post by:
Are dictionaries the same as hashtables?
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |