Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Is there any functions for sorted list? #182

Open
mola-T opened this issue May 18, 2016 · 6 comments · May be fixed by #244
Open

Is there any functions for sorted list? #182

mola-T opened this issue May 18, 2016 · 6 comments · May be fixed by #244
Labels
enhancement Suggestion to improve or extend existing behavior
Milestone

Comments

@mola-T
Copy link

mola-T commented May 18, 2016

Like inserting an element in a sorted list and returns the new sorted list

or

combining two sorted list and returns a new sorted list?

@Fuco1
Copy link
Collaborator

Fuco1 commented May 18, 2016

I don't think so. We can add -insert-sorted and -union-sorted which would use < for comparing and a -by versions which would also take a comparator.

Do you want to try to write a patch? (or anyone else? Otherwise I'll put it on my queue later this week)

@mola-T
Copy link
Author

mola-T commented May 18, 2016

Something like this?

(defun -insert-sorted (list item pred)
  (cond
   ((funcall pred item (car list))
    (-concat (cons item nil) list))
   ((funcall pred (car (last list)) item)
    (-concat list (cons item nil)))
   (t
    (let ((min 0)
          (max (- (length list) 1)))
      (while (> (- max min) 1)
        (if (funcall pred (nth (+ (/ (- max min) 2) min) list) item)
            (setq min (+ (/ (- max min) 2) min))
          (setq max (+ (/ (- max min) 2) min))))
      (-insert-at max item list)))))

@Fuco1
Copy link
Collaborator

Fuco1 commented May 18, 2016

Thanks! A couple notes though:

  1. Binary search is a nice idea, but with linked lists it's no better than just a linear scan (nth is O(n)), and much more complicated).
  2. Instead of (-concat (cons item nil) list) you can do (cons item list). Also (cons item nil) is the same as (list item)

I think something like using -split-with and then concating with the new item in the middle should work fine.

In general, dash guidelines are "clarity over speed" until someone complains it's too slow.

@mola-T
Copy link
Author

mola-T commented May 19, 2016

I am not sure whether a binary search is beneficial.

Binary search through link list : iteration is O(n) with comparison O(log n).

Linear scan: iteration is O(n) with comparison O(n).

I think there may be benefit when list is long or comparison is not a simple comparison, say comparing a string entry in a structure with case ignored or even string-lessp is not simple.

@Fuco1
Copy link
Collaborator

Fuco1 commented May 19, 2016

Right, but isn't your code binary search? Or we're misunderstanding each other.

@mola-T
Copy link
Author

mola-T commented May 20, 2016

Yeah binary search is still good when list is long or comparison is not a simple comparison.

When list is short, it doesn't matter what method we use.

Anyway, I leave the job for you. 😝

Finally, thanks for this awesome library, many other awesome packages can happen.
Thank you.

@Fuco1 Fuco1 added this to the 2.14.0 milestone Apr 24, 2017
@Fuco1 Fuco1 linked a pull request Oct 11, 2017 that will close this issue
2 tasks
@basil-conto basil-conto removed this from the 2.16.0 milestone Feb 15, 2021
@basil-conto basil-conto added enhancement Suggestion to improve or extend existing behavior and removed discussion labels Feb 15, 2021
@basil-conto basil-conto added this to the 2.19.0 milestone Feb 15, 2021
@basil-conto basil-conto modified the milestones: 2.19.0, 2.20.0 Jun 29, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement Suggestion to improve or extend existing behavior
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants