Topic: RemoveNth ...

[nivuahc]

Want for me to 'splain?

BRB (grabbin' a mug o' brew ...)

I do! I do!

[Mark]

Want for me to 'splain?

Oh heck yea!!

[MP]

Let's say we have a list of 3 items '(a b c) and we want to remove the 2nd, or 1th item (b).

Code: [Select]

(RemoveNth 1 '(a b c)) ...

(foo a):
    ;;  i = 0 after assignment, so this
    ;;  returns nil to vl-remove-if, iow,
    ;;  the current item is not removed
    (if (eq 1 (setq i (1+ i)))
        (defun foo (x) nil)
    )
   
(foo b):
    ;;  i = 1 after assignment, so this
    ;;  returns a new definition of foo
    ;;  which is also a non nil value,
    ;;  thus vl-remove-if removes this item
    ;;  from the list
    (if (eq 1 (setq i (1+ i)))
        (defun foo (x) nil)
    )

(foo c):
    ;;  for this and any remaining calls
    ;;  foo returns nil no matter what we
    ;;  throw at it, so vl-remove-if will
    ;;  not remove any more items
Make sense?

Can anyone see where there's room for optimization?

[Mark]

Make sense?

Ok.. now it does. Very cool stuff MP.

[Mark]

Can anyone see where there's room for optimization?

No I can't, at least not at this time.

[nivuahc]

Can anyone see where there's room for optimization?

I can!

First, you have to take into account the time of day --> early
Then you calculate how much coffee has been ingested --> approximately 20oz.
Do a little math, look at the code, and it's fairly easy to see that

Code: [Select]


(setq drink_more_coffee T)


is desperately needed.

[Mark]

Wait.... maybe if you stop the search after you get the first match?

[MP]

Make sense?

Ok.. now it does.

Very cool stuff MP.

Thanks man.

[Mark]

Wait.... maybe if you stop the search after you get the first match?

close or "no cigar" ?

[MP]

Close: You can't have vl-remove-if stop iterating the list once it starts, all one can do is try to optimize the predicate function, which is what I've done via (defun foo (x) nil) once the target has been realized.

There's still at least one other thing.

[MP]

If there were no overhead associated with reverse, consider this --

Code: [Select]

(defun RemoveNth ( n lst / len foo i )

    (defun foo (x)
        (if (eq n (setq i (1+ i)))
            (defun foo (x) nil)
        )  
    )

    (cond
        (   (zerop n) (cdr lst))
        (   (eq n (1- (setq len (length lst))))
            (reverse (cdr (reverse lst)))
        )
        (   (< (setq i -1) n len)
            (if (< n (1+ (/ len 2)))
                (vl-remove-if 'foo lst)
                (reverse
                    (RemoveNth (- len n 1)
                        (reverse lst)
                    )
                )
            )    
        )  
        (   lst  )
    )
   
)

[Mark]

That'll take a picture for me figure out.

[MP]

Hint -- it never has to count higher than half the length of the list.

[JohnK]

Hey nice trick!

Optomise huh?! well lets see... I think the first thing i would do is to test a while loop against the vl-remove-if and see which one whips thru faster. (You can stop a while loop while you cant a vl-remove so i would be intrested in seeing those results.) However if the while loop is faster then that would negate your fany defining trick.

If the vl-remove function is faster then i would test to see if a set-lambda is faster then a defun. (Which i kinda doubt, but i think its worth a shot if we can remove a bit of time associated with recaling the function definition.)

But if that fails then i would mabey tackle a tree type of recusrsion. (Operate ont the front and the back of the list at the same time. --BUT that would increase the stack a T O N! so that might not work out either.)

[MP]

Go crazy John.

Here's my non optimized vanilla lisp version (word wrap will kill it) --

Code: [Select]

(defun RemoveNth ( n lst / len key pair )
    (cond
        (   (zerop n) (cdr lst))
        (   (eq n (1- (setq len (length lst))))
            (reverse (cdr (reverse lst)))
        )
        (   (< (setq key -1.0) n len)
            (mapcar 'cdr
                (append
                    (reverse
                        (cdr
                            (member
                                (setq pair
                                    (nth n
                                        (setq lst
                                            (mapcar
                                               '(lambda (item)
                                                    (cons
                                                        (setq key
                                                            (1+ key)
                                                        )
                                                        item
                                                    )
                                                )
                                                lst            
                                            )
                                        )    
                                    )
                                )
                                (reverse lst)
                            )
                        )
                    )
                    (cdr (member pair lst))
                )
            )    
        )
        (   lst  )
    )
)
Haven't had time to bench any of this stuff, so I don't know what's faster. May prove intellestink!