On 28 Aug 2008, at 9:07 pm, Jules Bean wrote:
Insert for Data.Sequence is log(i) where i is the position of the
insertion; clearly bounded by log(n). toList is O(n) and index is
(at worst) log(i).
I think the corresponding operations with tries are log(n),
Let the key you want to insert h
Well, sure, that could work too.
--
_jsn
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Jason Dusek wrote:
Jules Bean <[EMAIL PROTECTED]> wrote:
Jason Dusek wrote:
Jules Bean <[EMAIL PROTECTED]> wrote:
Jason Dusek wrote:
I would much rather have a pure Trie that is foldable.
If we have a Trie, we get a space efficient sorted list,
too.
Well, Data.Sequence can be used as a space
Jules Bean <[EMAIL PROTECTED]> wrote:
> Jason Dusek wrote:
> > Jules Bean <[EMAIL PROTECTED]> wrote:
> > > Jason Dusek wrote:
> > > > I would much rather have a pure Trie that is foldable.
> > > > If we have a Trie, we get a space efficient sorted list,
> > > > too.
> > >
> > > Well, Data.Sequence
On Aug 27, 2008, at 4:31 PM, Bulat Ziganshin wrote:
Hello Jan-Willem,
Wednesday, August 27, 2008, 4:06:11 PM, you wrote:
One obvious way to make non-modifiable hash tables useful is to "eat
your own tail" non-strictly--- aggregate a set of hash table entries,
construct a hash table from them
Jason Dusek wrote:
> Jules Bean <[EMAIL PROTECTED]> wrote:
>> Jason Dusek wrote:
>>> I would much rather have a pure Trie that is foldable. If we
>>> have a Trie, we get a space efficient sorted list, too.
>> Well, Data.Sequence can be used as a space efficient sorted
>> list which is Foldable - i
Jules Bean <[EMAIL PROTECTED]> wrote:
> Jason Dusek wrote:
> > I would much rather have a pure Trie that is foldable. If we
> > have a Trie, we get a space efficient sorted list, too.
>
> Well, Data.Sequence can be used as a space efficient sorted
> list which is Foldable - if you make the decision
Hello Don,
Thursday, August 28, 2008, 10:32:43 AM, you wrote:
> Seems like you can make a pure hashtable by unsafePerformIO on the
> impure one, and exporting only 'lookup'..
probably yes, but it will lose a bit of performance due to incremental
building of hashtable. actually, writing HT module
bulat.ziganshin:
> Hello Richard,
>
> Thursday, August 28, 2008, 5:28:46 AM, you wrote:
>
> >>> trie: O(len)*O(width)
> >>> hashed trie: O(len)
> >>> hash: O(len)
>
> > If "width" here refers to the branching factor of the trie,
> > it's actually O(len.lg(width)), and the width that matters
> >
Hello Richard,
Thursday, August 28, 2008, 5:28:46 AM, you wrote:
>>> trie: O(len)*O(width)
>>> hashed trie: O(len)
>>> hash: O(len)
> If "width" here refers to the branching factor of the trie,
> it's actually O(len.lg(width)), and the width that matters
> is not the *possible* number of choices
Jason Dusek wrote:
I would much rather have a pure Trie that is foldable. If we
have a Trie, we get a space efficient sorted list, too.
Well, Data.Sequence can be used as a space efficient sorted list which
is Foldable - if you make the decision to insert elements into it in a
sorted way
I would much rather have a pure Trie that is foldable. If we
have a Trie, we get a space efficient sorted list, too.
--
_jsn
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Someone wrote:
trie: O(len)*O(width)
hashed trie: O(len)
hash: O(len)
If "width" here refers to the branching factor of the trie,
it's actually O(len.lg(width)), and the width that matters
is not the *possible* number of choices but the *actual*
number.
The great problem with hash tables is d
Hello Jules,
Wednesday, August 27, 2008, 7:59:55 PM, you wrote:
>>> To get "much better efficient" than a trie, the hash function has to be
>>> so fast that it is faster than following (log n) pointers
>>
>> afaiu, trie search follows n pointers
> No.
> "n" is the number of strings in my data
Hello Jan-Willem,
Wednesday, August 27, 2008, 4:06:11 PM, you wrote:
> One obvious way to make non-modifiable hash tables useful is to "eat
> your own tail" non-strictly--- aggregate a set of hash table entries,
> construct a hash table from them, and plumb the resulting hash table
> into the o
Hello Stephan,
Wednesday, August 27, 2008, 1:52:23 PM, you wrote:
> and on the other and, its implementation uses hash functions and arrays
> as well. IIRC it does that in a state monad that keeps the array mutable
> and finally freezes it before usage, which might be a good idea for pure
> hash t
Hello Daniel,
Wednesday, August 27, 2008, 8:01:24 PM, you wrote:
>> trie: O(len)*O(width)
>> hashed trie: O(len)
>> hash: O(len)
> Wouldn't the hashtable have lookup time O(len+bucketsize)?
i suppose that bucketsize=O(1): constructor should get [approximate]
size of hashed assoclist and it will
Bulat Ziganshin wrote:
Hello Jules,
Wednesday, August 27, 2008, 7:21:46 PM, you wrote:
given these constraints, it should be just a 10-20 lines of code, and provide
much better efficiency than any tree/trie implementations
Prove it.
To get "much better efficient" than a trie, the hash f
Am Mittwoch, 27. August 2008 17:36 schrieb Bulat Ziganshin:
> Hello Jules,
>
> Wednesday, August 27, 2008, 7:21:46 PM, you wrote:
> >> given these constraints, it should be just a 10-20 lines of code, and
> >> provide much better efficiency than any tree/trie implementations
> >
> > Prove it.
> >
>
On Wed 2008-08-27 16:21, Jules Bean wrote:
> Bulat Ziganshin wrote:
>> Hello haskell-cafe,
>>
>> solving one more task that uses English dictionary, i've thought: why we
>> don't yet have pure hashtable library? There is imperative hashtables,
>> pretty complex as they need to rebuild entire tabl
Hello Jules,
Wednesday, August 27, 2008, 7:21:46 PM, you wrote:
>> given these constraints, it should be just a 10-20 lines of code, and
>> provide much better efficiency than any tree/trie implementations
> Prove it.
> To get "much better efficient" than a trie, the hash function has to be
>
Bulat Ziganshin wrote:
Hello haskell-cafe,
solving one more task that uses English dictionary, i've thought: why we don't
yet have pure hashtable library? There is imperative hashtables, pretty complex
as they need to rebuild entire table as it grows. There is also simple assoc
lists and tree
On Aug 27, 2008, at 3:41 AM, Bulat Ziganshin wrote:
Hello haskell-cafe,
solving one more task that uses English dictionary, i've thought:
why we don't yet have pure hashtable library? There is imperative
hashtables, pretty complex as they need to rebuild entire table as
it grows. There is
>> * hashtable is represented as an array of assoc lists: Array Int [(a,b)]
>
> Don't immutable arrays get rather inefficient when modified?
Bulat was specifically asking for "simple *non-modifiable* hashes"
http://article.gmane.org/gmane.comp.lang.haskell.cafe/43612
J.W.
signature.asc
Descr
Bulat Ziganshin wrote:
> solving one more task that uses English dictionary, i've thought: why we
> don't yet have pure hashtable library? There is imperative hashtables,
> [...]
> how should it look:
>
> * hashtable is represented as an array of assoc lists: Array Int [(a,b)]
Don't immutable arr
On 27 Aug 2008, at 10:39, Bayley, Alistair wrote:
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Thomas Davie
> Much better efficiency in what way?
instead of going through many levels of tree/trie,
lookup function will just select array element by hash value
> From: [EMAIL PROTECTED]
> [mailto:[EMAIL PROTECTED] On Behalf Of Thomas Davie
>
> > Much better efficiency in what way?
>
> instead of going through many levels of tree/trie,
> lookup function will just select array element by hash value
> and look through a few elements in ass
On 27 Aug 2008, at 10:09, Bulat Ziganshin wrote:
Hello Jason,
Wednesday, August 27, 2008, 11:55:31 AM, you wrote:
>> given these constraints, it should be just a 10-20 lines of
>> code, and provide much better efficiency than any tree/trie
>> implementations
> Much better efficiency in wha
Hello Jason,
Wednesday, August 27, 2008, 11:55:31 AM, you wrote:
>> given these constraints, it should be just a 10-20 lines of
>> code, and provide much better efficiency than any tree/trie
>> implementations
> Much better efficiency in what way?
instead of going through many levels of tree/
Bulat Ziganshin <[EMAIL PROTECTED]>:
> given these constraints, it should be just a 10-20 lines of
> code, and provide much better efficiency than any tree/trie
> implementations
Much better efficiency in what way?
--
_jsn
___
Haskell-Cafe mailing lis
Hello haskell-cafe,
solving one more task that uses English dictionary, i've thought: why we don't
yet have pure hashtable library? There is imperative hashtables, pretty complex
as they need to rebuild entire table as it grows. There is also simple assoc
lists and tree/trie implementations, bu
31 matches
Mail list logo
