Thank you for the info, however ...
Though symbols are implemented with hash tables internally, they can't
function as a general dictionary.
Moreover, x i. y takes linear time, which is not constant time O(1),
which is the characteristics of hashing.
2006/9/18, Mike Day <[EMAIL PROTECTED]>:
June, have you looked at the Symbol mechanism accessible
with the primitive s: ?
See the dictionary page
system/extras/help/dictionary/dsco.htm#spacetime
These examples under the "Space & Time" section talk about
linear time for look-up, but I think it means O(n) where
n is the number of symbols being queried.
"Computations on symbols generally require linear time.
Specifically:
query (new) O((len y) * ^. 0 s: 0)
query (old) O(len y)
/:y O(*/$y)
i{y O((*/$i) * */}.$y)
x < y etc. O(x >.&(*/@$) y)
x i. y O(x + &(*/@$) y)"
Mike
Pascal Jasmin wrote:
> to get O(1) lookup, you can use sparse arrays.
> if you don't have numeric keys, you need a function
> that will map 1to1 text keys to a number (simplest
> such function concatenates ascii values).
>
> --- June Kim <[EMAIL PROTECTED]> wrote:
>
>
>> Hello.
>>
>> I have asked if there is hash facility in J for a
>> couple of times. At
>> first, I thought J's dict class(j-n/z/w-dict) was
>> one. However, it
>> isn't. (actually, dictionary = map = hash across
>> many modern
>> programming languages)
>>
>> Since the key/value table is dynamically updated,
>> m&i. code
>> specialization doesn't work(the dict implementation
>> doesn't use that
>> code either) and hence the lookup time is O(N),
>> instead of O(1), which
>> is expected for real hash implementations.
>>
>> In this reason, dict class is inhibitively expensive
>> for using like a
>> dictionary in spite of the name and its name may
>> confuse J novices.
>>
>> Does any one have real hash implementations in J? If
>> not, I might have
>> to start to make one.
>>
>> June
>>
>>
> ----------------------------------------------------------------------
>
>> For information about J forums see
>> http://www.jsoftware.com/forums.htm
>>
>>
>
>
> __________________________________________________
> Do You Yahoo!?
> Tired of spam? Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
>
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
