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
