Quickest 'replace on nested lists?

newdep · Post by **newdep** » Fri Jun 01, 2007 9:29 pm

Im currently fighting an issue ;-)
(probably easy to fix but i dont see it..)

I have 2 lists..

'one = 30000 total entry's (single list)
'two = 1000000 total entry's (nested list, 30000 entry's with all 1 sub-list)

Now i want to replace all occeurences from list 'one in nested list 'two.
(everything, including the nested lists..thus 'ref-all if the choise here..)

When i do it like this its very very slow ->

(map (fn(q) (map (fn(r) (nth-set (two r) "-bye-")) (ref-all q two))) one)
(That is because of the nested 'map)

this is very quick ->
(map (fn(r) (nth-set (two r) "-bye-")) (ref-all "this one" two))
(single map, but only replacing 1 value "this one" instead of the whole 'one)

I dont want to use 'dolist because thats too slow..
I cant use replace-assoc because its not an assoc list.
I cant use 'replace because that cant handle imlpicet-indexing.
Also 'match and 'unify seem not to provide a solution, i could be wrong!

So is there a complete different way of replacing all values from 'one in a nested list 'two by doing it in a one-liner?

addon: both lists contain strings only.

addon 2: It must be destuctive because of memory usage

Norman.

Jeff · Post by **Jeff** » Sat Jun 02, 2007 12:25 am

Maybe try a while loop. Other than that, I can't see any better applicative way of doing it. Of course, real men recurse, but that is not the issue here :)

Jeff · Post by **Jeff** » Sat Jun 02, 2007 1:12 am

Is list two like (("x" ("y" "z"))...) or (("x" "y" "z")...)?

Jeff · Post by **Jeff** » Sat Jun 02, 2007 2:37 am

I tried several different ways, but iteration beat applicative by about 10%. Granted, I did this on lists 1/10 the size, but that's because I'm on an old G4 powerbook at 1.2GHz and with little enough RAM that I'd be too embarrassed to specify it here :).

Using map or recursion is the elegant method. Unfortunately, expressive > efficient > elegant > idiomatic. It's more important that the solution work well than that it be pretty.

Code: Select all

(set 'relacement "FOO")
(dolist (o one)
  (dolist (r (ref-all o two))
    (nth-set (two r) replacement)))

PS remember to assign the replacement ahead of time so you don't end up re-creating a temporary space for it over and over again. It's a small overhead, but it probably helps ;)

newdep · Post by **newdep** » Sat Jun 02, 2007 6:22 am

Thanks for the reply's jeff...

The second list is like this (kind of a relational-list to list 'one)
'( "someting" '( "and' "here" "is" "somethnig "else" .... ) "another" '( "thing" ....))

I could not find a function in newlisp that apply's a list to another list , there are a lot of function that apply an expression of function to a list but thats not what
helps as a replace finaly...so i started with 'map and because 'dolist is slow in this case i skipped that.. Because of all the list functions i thought it would be possible to skip the loop functions..but i think i cant get around this, but i do hope so ;-)

all values in list 'two will eventualy be replaced by its index in list 'one.. so that finaly list 'one is the content and list two only an indexed-list.

On none nested lists this is easy done, but on a nested list (ref-all) im realy
getting into speed problems..but then again... newlisp is always surpricing me
with a easyness of handling it...(for now..i did not find it ;-)

Norman.