October 2009 - Pharo-dev - lists.pharo.org

Re: [Pharo-project] HashTable vs Dictionary

by Igor Stasenko

2009/10/22 Andres Valloud <avalloud(a)smalltalk.comcastbiz.net>: > Igor et al, >> That's why each of implementations (Dictionary and HashTable) having own niche. >> For small sizes, dictionaries in their current state is best. >> For bigger sizes, one could choose to use HashTable, or any other >> implementation, which may fit better. >> > > As long as this refers to objects that implement #hash as #identityHash, > yes. Â If you can produce a (reasonably efficient) hash function that has > very few collisions, then open addressing with linear probing (the usual > implementation of Set/Dictionary) tends to be the most efficient. > Well, you can always attack the problem from different side - create a Set and Dictionary which using a perfect hash algorythms. As you may know, a perfect hash is a function which producing unique values for a limited set of elements. So, that in sets hashed using perfect hash function, no collisions possible, and hence the access time to any element is O(1). The drawback of such approach, that finding a perfect hash function for a set of elements is time consuming (best ones, AFAIK, consuming O(k*n) time, where n is number of elements), so you would never want to use a perfect hashing for collections which tend to grow or shrink often. But for collections, which populated once, and then used for read-only access this is worth doing. And its quite easy to modify current classes to use a perfect hash: just add a perfectHash ivar to it, and if its not nil , then use it to find an index of item. And if perfectHash is nil, then we just use the current implementation. And of course, you need to implement a perfect hash search, which standing aside :) But then you could just do: set := something collect: [... ] asSet rehashWithPerfectHash. and voila, you got a set with no collisions :) > Andres. > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig.

Oct. 22, 2009

Re: [Pharo-project] HashTable vs Dictionary

by Andres Valloud

Igor et al, > That's why each of implementations (Dictionary and HashTable) having own niche. > For small sizes, dictionaries in their current state is best. > For bigger sizes, one could choose to use HashTable, or any other > implementation, which may fit better. > As long as this refers to objects that implement #hash as #identityHash, yes. If you can produce a (reasonably efficient) hash function that has very few collisions, then open addressing with linear probing (the usual implementation of Set/Dictionary) tends to be the most efficient. Andres.

Oct. 22, 2009

Re: [Pharo-project] HashTable vs Dictionary

by Igor Stasenko

2009/10/21 Lukas Renggli <renggli(a)gmail.com>: >> yyyyyyyyeeeeeeeeeeesssssssssssssssssssssssss >> and get linearrrrrrrrrrrrrrrrrrrrrly boring and slow. > > Yes, but only if your objects don't implement #hash properly. HashMap > trades space and time to get O(1) behavior IF you have lots of > elements with bad hash values. If the hash values are good (which is > the case most of the time) or if you have not that many elements > (which is the case most of the time), it is a waste of time and space > though. > Right. That's why each of implementations (Dictionary and HashTable) having own niche. For small sizes, dictionaries in their current state is best. For bigger sizes, one could choose to use HashTable, or any other implementation, which may fit better. Ultimately, there is no solution which is best in all cases (space, access time, insertion/remove time etc). > Lukas > > -- > Lukas Renggli > http://www.lukas-renggli.ch > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig.

Oct. 22, 2009

Re: [Pharo-project] HashTable vs Dictionary

by Martin McClure

StÃ©phane Ducasse wrote: [...] >> With changes along these lines, I agree with Andres that linear- >> probing >> collections should be able to equal or beat the performance of chained >> collections, and are a better choice for general-purpose collections. >> >> Regards, >> >> -Martin > > Martin > don;t you have some changes so that we could try :) Sigh. Too many projects... But I'll try to get you something. Andres' post had some good suggestions that will change what I implement. -Martin

Oct. 21, 2009

Re: [Pharo-project] MC 1.6 status?

by keith

>> > I am always want more :) fair enough > Here the vision what i having: > > - take a minimal kernel image (Pavel's works going in mind) I always intended to do this, but I never got pavels images to work on mac osx. > - load LPF there, make it work, make sure that it could load any MC > packages after that The normal minimal dependancy is on Network, and Compression, however if files are available locally it would only be compression, however the current implementation looks on squeaksource for things. > - use a version control for LPF script (put it on SVN somewhere) In previous versions LPF.st needed to be updated in order to keep current. Now that Installer can grab the latest mcz and file in the source.st within, it can get the latest every time and is less in need of updating and explicit version control. > - continue efforts on making LPF become an extremely modular and > self-sufficient piece of software, be my guest. I have always maintained that it is the concept that is the important thing, if you can get buy in to the concept then the rest is easy. I hope you succeed where I have failed. Keith

Oct. 21, 2009

[Pharo-project] Alien-Core-kdt.59

by Ken Treis

AlienWeakTable sends #copyGrownBy: to both of its internal arrays, but it looks like neither Squeak nor Pharo implement it in the collection hierarchy. Pharo has #grownBy:, but Squeak doesn't. So in Alien-Core- kdt.59, I implemented SequenceableCollection>>copyGrownBy: by copying in the Pharo implementation of #grownBy:. This should solve some nastiness that could happen when the table hit its initial maximum (1024 objects). -- Ken Treis Miriam Technologies, Inc.

Oct. 21, 2009

Re: [Pharo-project] MC 1.6 status?

by Igor Stasenko

2009/10/22 keith <keith_hodges(a)yahoo.co.uk>: > What more do you want? > I am always want more :) Here the vision what i having: - take a minimal kernel image (Pavel's works going in mind) - load LPF there, make it work, make sure that it could load any MC packages after that - use a version control for LPF script (put it on SVN somewhere) - continue efforts on making LPF become an extremely modular and self-sufficient piece of software, with very small dependencies from environment (only basic classes, like collections and most basic I/O - files and/or sockets) > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig.

Oct. 21, 2009

Re: [Pharo-project] MC 1.6 status?

by keith

What more do you want?

Oct. 21, 2009

Re: [Pharo-project] feedback about the "new inspector"

by Niko Schwarz

Hi Johan, On 21.10.2009, at 18:39, Johan Brichau wrote: > I also understood from Niko on monday that he is working on an > alternative inspector that very much ressembles the one from > Visualworks. Yes, with Toon Verwaest, it should get ready on the weekend. :) Niko

Oct. 21, 2009

[Pharo-project] Stack re-implemented

by Niko Schwarz

Hi list, issue 1336 proposes re-implementing Stack using the new LinkedList which can take arbitrary objects. I committed the code and it was really straightforward to do. Now stack is implemented in 3 one-line methods, removing about 10 methods, and removing one class (StackLink). Please see http://code.google.com/p/pharo/issues/detail?id=1336 or SLICE-issue-1336-StackReimplemented-NikoSchwarz.2. in the inbox. Cheers, Niko

Oct. 21, 2009