Topic: Efficiently split a list by list of indexes

[HeavyThumper]

There may be a better way of expressing this - but given a list of values, and a separate list of indices of that list, I want to create two new lists - one that contains the values not referenced, and one that does. To try to clarify:

Code - Auto/Visual Lisp: [Select]

1. (setq thelist "alpha" "bravo" "charlie" "delta" "echo")
2. (setq indices 1 3) ; assuming indices are zero-based
3.  
4. ; magic processing here to create two new lists: included and notincluded
5.  
6. (princ included)
7. bravo delta
8.  
9. (princ notincluded)
10. alpha charlie echo
11.  

I can think of a few methods to accomplish this - but as a mere Lisp dabbler I don't know if there's some features I can leverage to make this both easier and execute faster. At first, I'm thinking of a brute force method - at least it executes via a single pass.

Below is a function I've written that...functions. It does (on initial testing) exactly what I want. But - I gotta believe there's a better way to accomplish this. I do leverage one of Lee Mac's excellent functions for this.

Code - Auto/Visual Lisp: [Select]

1. ;; Passed a list of values, and a list of indices, return a list containing
2. ;; first the list of values referenced by the indices, and second the list
3. ;; not so contained.
4. (defun split_via_indices ( thelist indices / ilist nlist item i )
5.   (setq i 0)
6.  
7.   (repeat (length thelist)
8.     (cond
9.       ( (member (itoa i) indices)
10.         (setq ilist (cons ilist (nth i thelist)))
11.       )
12.       (t
13.         (setq nlist (cons nlist (nth i thelist)))
14.       )
15.     )
16.     (setq i (1+ i))
17.   )
18.  
19.   (setq ilist (vl-sort (LM:flatten-nils ilist) '<))
20.   (setq nlist (vl-sort (LM:flatten-nils nlist) '<))
21.   (cons ilist nlist)
22. )
23.  
24. (defun btnSel ()
25.   (setq lst_highlighted (get_tile "lb_available"))
26.   (setq lst_split (split_via_indices lst_available (LM:str->lst lst_highlighted " ")))
27.   (setq lst_selected (list lst_selected (car lst_split)))
28.   (setq lst_selected (LM:flatten-nils lst_selected))
29.   (setq lst_selected (vl-sort (LM:Unique lst_selected) '<))
30.   (setq lst_available (cdr lst_split))
31.   (update_listbox "lb_available" lst_available)
32.   (update_listbox "lb_selected" lst_selected)
33. )
34.  

Note the "cleanup" lines after the split function - I need to re-sort after merging. Which really bothers me but I don't know how to do it correctly. Being able to "natively" generate "clean" lists - without having to filter them through Lee's function would be great.

Now - the astute reader may have figured out I'm using this in a DCL listbox context...in which case there may be a totally different way of accomplishing this that bypasses some of the steps I'm taking. I'm open to suggestions in that area as well - though that probably should be under a different thread. At the moment I have created a (I think) functional dual listbox dialog of the familiar "choose things from the left and show them on the right" variety. I haven't seen explicit examples of this - just enough inferences that let me stumble my way through to my own version.

Next I get to try to actually alter the drawing based on the dialog selections...

[roy_043]

There are some issues with your code. For one thing you do not use the cons function properly.
Following the basic algorithm suggested by you, the split_via_indices can/should look like this IMO:

Code - Auto/Visual Lisp: [Select]

1. ; (setq thelist '("alpha" "bravo" "charlie" "delta" "echo"))
2. ; (setq indices '(1 3))
3.  
4. (defun split_via_indices (thelist indices / ilist nlist i)
5.   (setq i 0)
6.   (foreach itm thelist
7.     (if (vl-position i indices)
8.       (setq ilist (cons itm ilist))
9.       (setq nlist (cons itm nlist))
10.     )
11.     (setq i (1+ i))
12.   )
13.   (list (reverse ilist) (reverse nlist))
14. )

[HeavyThumper]

First, thank you. Took a little bit to (slightly) understand what you were doing - I'm still not used to the lisp (if construct. But I got it.

As I didn't explicitly specify you're forgiven for not knowing. Next time you'll be expected to be inside my head and knowing the full context of any code excerpts I post . The list "indices" is a list of strings - therefore I needed to modify the comparison:

Code - Auto/Visual Lisp: [Select]

1. (if (vl-position (itoa i) indices)
2.  

and then after fixing the calling function - it works again. Thank you.

Now let's look at the calling function:

Code - Auto/Visual Lisp: [Select]

1. (setq lst_split (split_via_indices lst_available (LM:str->lst lst_highlighted " ")))
2. ; (car lst_split) contains highlighted values from available box -
3. ; must ADD to, not replace, values in selected listbox.
4. (setq lst_selected (cons (car lst_split) lst_selected))
5. ; fix into a clean list
6. (setq lst_selected (LM:flatten-nils lst_selected))
7. ; go ahead and sort as well
8.  (setq lst_selected (vl-sort (LM:Unique lst_selected) '<))
9. ;;
10. ;; Note below line - with the new version of split_via_indices I no
11. ;; longer use "cdr" - now need to use "cadr".
12. ;;
13. (setq lst_available (cadr lst_split))
14.  

Let's say the return of split_via_indices is (("alpha" "bravo") ("charlie" "delta" "echo")). I found that on executing (cdr lst_split), the result was (("charlie" "delta" "echo")). I needed to use (cadr lst_split) to get ("charlie" "delta" "echo").

I don't understand why - probably something fundamental which I'm missing.

[ronjonp]

Here's another for fun:

Code - Auto/Visual Lisp: [Select]

1. (defun _foo (thelist indices / a r)
2.   (foreach i (reverse indices)
3.     (if (setq a (nth i thelist))
4.       (setq r       (cons a r)
5.             thelist (vl-remove a thelist)
6.       )
7.     )
8.   )
9.   (list r thelist)
10. )
11. (_foo '("alpha" "bravo" "charlie" "delta" "echo") '(1 3))
12. ;; (("bravo" "delta") ("alpha" "charlie" "echo"))
13.  

[HeavyThumper]

Uh...right. Of course. Obvious.

Ok..let's see if I can follow what you're doing. First, you're parsing the list of indices - instead of the list of source items. Which means...probably much faster operation as the selected indices are going to be less that the source list. Make sense.

Now you're...selecting an item from the list and if it's non-nil continue. Then you add to the include list. And at the same time delete from the source list...yielding the not-included list on finish. Simple.

Couple questions come up:

1. What is the purpose of the initial (reverse)? Because these lists (at least one of them) themselves get added to other lists later the order is irrelevant - I'll need to run a sort afterwards regardless.

2. The apparently redundant (setq a (nth i thelist)) in the (cons - was that a simple oversight in a quick post or were you waiting to see if I caught it? Or is there a purpose I'm not seeing?

3. My initial setup has "indices" as strings - so I needed to adjust (nth i thelist) into (nth (atoi i) thelist). However - that had a side effect that if the "indices" list is empty - the function will always select the first item. I started with these lines in the calling function:

Code - Auto/Visual Lisp: [Select]

1. (setq lst_highlighted (get_tile "lb_available"))
2. (setq lst_split (split_via_indices2 lst_available (LM:str->lst lst_highlighted " ")))

and changed to:

Code - Auto/Visual Lisp: [Select]

1. (setq lst_highlighted (get_tile "lb_available"))
2. (setq indices (read (strcat "(" lst_highlighted ")")))
3. (setq lst_split (split_via_indices2 lst_available indices))

Now I no longer need the (atoi) in the split function and all is well.

4. In terms of "expense" - how much overhead does "vl-remove" add to the processing? I'm assuming since you recommended it it's a good choice - for some reason I got it stuck in my head that the "vl-" functions in general are "bad" and additionally I somehow thought direct list manipulation would be expensive as well. I'm probably wrong thinking all around - I'd appreciate a cognitive recalibration here.

[ronjonp]

Uh...right. Of course. Obvious.

Ok..let's see if I can follow what you're doing. First, you're parsing the list of indices - instead of the list of source items. Which means...probably much faster operation as the selected indices are going to be less that the source list. Make sense.

Now you're...selecting an item from the list and if it's non-nil continue. Then you add to the include list. And at the same time delete from the source list...yielding the not-included list on finish. Simple.

Couple questions come up:

1. What is the purpose of the initial (reverse)? Because these lists (at least one of them) themselves get added to other lists later the order is irrelevant - I'll need to run a sort afterwards regardless.

2. The apparently redundant (setq a (nth i thelist)) in the (cons - was that a simple oversight in a quick post or were you waiting to see if I caught it? Or is there a purpose I'm not seeing?

3. My initial setup has "indices" as strings - so I needed to adjust (nth i thelist) into (nth (atoi i) thelist). However - that had a side effect that if the "indices" list is empty - the function will always select the first item. I started with these lines in the calling function:

Code - Auto/Visual Lisp: [Select]

1. (setq lst_highlighted (get_tile "lb_available"))
2. (setq lst_split (split_via_indices2 lst_available (LM:str->lst lst_highlighted " ")))

and changed to:

Code - Auto/Visual Lisp: [Select]

1. (setq lst_highlighted (get_tile "lb_available"))
2. (setq indices (read (strcat "(" lst_highlighted ")")))
3. (setq lst_split (split_via_indices2 lst_available indices))

Now I no longer need the (atoi) in the split function and all is well.

4. In terms of "expense" - how much overhead does "vl-remove" add to the processing? I'm assuming since you recommended it it's a good choice - for some reason I got it stuck in my head that the "vl-" functions in general are "bad" and additionally I somehow thought direct list manipulation would be expensive as well. I'm probably wrong thinking all around - I'd appreciate a cognitive recalibration here.

1. The reverse was there so CONS would place the indexed items in the same order. This could be achieved with a reverse at the end too though.
2. I set 'a' so (vl-remove a thelist) in the next line processes it *edit now I see that it was set twice modified above.
One caveat to vl-remove is if you have duplicate items in the list it zaps them all .. try:

Code - Auto/Visual Lisp: [Select]

1. (vl-remove "charlie" '("charlie" "charlie" "charlie" "charlie" "tango"))

5. vl-remove is pretty fast not sure where you got the idea that vl functions are bad ?

Quick benchmark and it's a tie!

Code - Auto/Visual Lisp: [Select]

1. SPLIT_VIA_INDICES
2. _FOO
3. ("alpha" "bravo" "charlie" "delta" "echo" "tango") Benchmarking ...................Elapsed milliseconds / relative speed for 65536 iteration(s):
4.  
5.     (_FOO L (QUOTE (0 1 3 4)))..................1766 / 1.00 <fastest>
6.     (SPLIT_VIA_INDICES L (QUOTE (0 1 3 4))).....1766 / 1.00 <slowest>
7.  
8.  
9. ; 4 forms loaded from #<editor "<Untitled-1> loading...">
10. _$

[steve.carson]

1. The reverse was there so CONS would place the indexed items in the same order. This could be achieved with a reverse at the end too though.

I think in this case the reverse needs to be where it is so the indices list gets processed big to small. Otherwise the nth's get messed up as you start taking items off the front of the list. Unless we can guarantee that the indices list will always be chronologically sorted small to large from the start, you may want to sort it first (big to small) instead of reversing.

[ronjonp]

1. The reverse was there so CONS would place the indexed items in the same order. This could be achieved with a reverse at the end too though.

I think in this case the reverse needs to be where it is so the indices list gets processed big to small. Otherwise the nth's get messed up as you start taking items off the front of the list. Unless we can guarantee that the indices list will always be chronologically sorted small to large from the start, you may want to sort it first (big to small) instead of reversing.

Good point .. maybe a (vl-sort  indices '>)

[Lee Mac]

I wanted to play too -

Code - Auto/Visual Lisp: [Select]

1. (defun foo2 ( i l / m n r )
2.     (setq n -1 r (vl-remove-if '(lambda ( x ) (if (vl-position (setq n (1+ n)) i) (setq m (cons x m)))) l))
3.     (list (reverse m) r)
4. )

Code - Auto/Visual Lisp: [Select]

1. _$ (foo2 '(1 3) '("alpha" "bravo" "charlie" "delta" "echo"))
2. (("bravo" "delta") ("alpha" "charlie" "echo"))

[bruno_vdh]

Hello,
For the game

Code: [Select]

(defun foo (x i l / res)
  (cond ((null i) (list nil l))
((= x (car i))
(setq res (foo (1+ x) (cdr i) (cdr l)))
(cons (cons (car l) (car res)) (cdr res))
)
(T
(setq res (foo (1+ x) i (cdr l)))
(list (car res) (cons (car l) (cadr res)))
)
  )
)

Code: [Select]

_$ (foo 0 '(1 3) '("alpha" "bravo" "charlie" "delta" "echo"))
(("bravo" "delta") ("alpha" "charlie" "echo"))


[ronjonp]

And the speed results ( could not test Bruno's kept crashing "internal stack limit reached (simulated)" )

ROY_SPLIT_VIA_INDICES
LEE_FOO2
RJP_FOO
(1 3) Benchmarking ...................Elapsed milliseconds / relative speed for 65536 iteration(s):

    (RJP_FOO L I)...................1125 / 2.76 <fastest>
    (ROY_SPLIT_VIA_INDICES L I).....1235 / 2.52
    (LEE_FOO2 L I)..................3110 / 1.00 <slowest>

 
; 6 forms loaded from #<editor "<Untitled-0> loading...">
_$

[JohnK]

Not the most efficient entry--the entry (_FOO) that doesn't actually iterate the list will be more efficient--but simple enough to be "fairly quick".

BTW, I like the methodology of FOO as well.

Code - Auto/Visual Lisp: [Select]

1. (defun split-from-list ( list_indices list_list / counter list_left list_right )
2.     (setq counter '()
3.           counter 0)
4.     (foreach item list_list
5.         (if (member counter list_indices)
6.             (setq list_right (cons item list_right))
7.             (setq list_left (cons item list_left)))
8.         (setq counter (1+ counter)))
9.     (list (reverse list_right) (reverse list_left)) )

Code: [Select]

(split-from-list '(1 3) '("alpha" "bravo" "charlie" "delta" "echo"))

Command: (split-from-list '(1 3) '("alpha" "bravo" "charlie" "delta" "echo"))
(("bravo" "delta") ("alpha" "charlie" "echo"))

Code: [Select]

Elapsed milliseconds / relative speed for 32768 iteration(s):

    (_FOO THELIST INDICIES)..................1172 / 2.60 <fastest>
    (FOO 0 INDICIES THELIS)..................1172 / 2.60
    (SPLIT-FROM-LIST INDICIES THELIST).......1266 / 2.41
    (SPLIT_VIA_INDICES THELIST INDICIES).....1312 / 2.32
    (FOO2 INDICIES THELIST)..................3047 / 1.00 <slowest>
 ---- Benchmark utility: In memory of Michael Puckett ----

[ronjonp]

---- Benchmark utility: In memory of Michael Puckett ----

I like that 

[JohnK]

---- Benchmark utility: In memory of Michael Puckett ----

I like that 

Me too. Add this to your version.

Code - Auto/Visual Lisp: [Select]

328.         (mapcar
329.           'write-line
330.           '(" ---- Benchmark utility: In memory of Michael Puckett ----"
331.             " "))
332.  
333.         (princ)
334.  
335.     )
336.  
337.     ;;=================================================================
338.     ;;
339.     ;;  Program is defined, let's rock and roll ...
340.     ;;
341.     ;;=================================================================
342.  
343.     (_Main statements)
344.  

[ronjonp]

Already done