Sort a list from another list IDs

Question

I have a list with some identifiers like this:

List<long> docIds = new List<long>() { 6, 1, 4, 7, 2 };

Morover, I have another list of <T> items, which are represented by the ids described above.

List<T> docs = GetDocsFromDb(...)

I need to keep the same order in both collections, so that the items in List<T> must be in the same position than in the first one (due to search engine scoring reasons). And this process cannot be done in the GetDocsFromDb() function.

If necessary, it's possible to change the second list into some other structure (Dictionary<long, T> for example), but I'd prefer not to change it.

Is there any simple and efficient way to do this "ordenation depending on some IDs" with LINQ?

are you assured that every `docId` occurs exactly once in `docs`, what property will hold the `Id` or will a selector `Func` be required? — Jodrell, Mar 07 '13 at 15:43
Does the first list represent a "master list"? Another words, will the second list be a subset representing a portion (or the entirety) of the first list? — code4life, Mar 07 '13 at 16:00

score 471 · Accepted Answer · answered Mar 07 '13 at 15:42

471

docs = docs.OrderBy(d => docsIds.IndexOf(d.Id)).ToList();

answered Mar 07 '13 at 15:42

Denys Denysenko

7,598
1
20
30

@Kaf thats why I upvoted too, does rely on knowing the document ID property is called `Id`. Its not specified in the question. – Jodrell Mar 07 '13 at 16:13
4

@BorjaLópez, a quick note. You mention efficiency in your question. `IndexOf` is perfectly acceptable for your example and nice and simple. If you had a lot of data my answer might be better suited. http://stackoverflow.com/questions/3663014/why-is-this-list-indexof-code-so-much-faster-than-the-listi-and-manual-compa – Jodrell Mar 07 '13 at 17:20
I've benchmarked this method and the one with the Dictionary (see below) and it's almost twice as fast. – Michael Logutov Apr 01 '14 at 05:51
2

@DenysDenysenko Fantastic. Thanks so much; exactly what I was looking for. – silkfire Jan 27 '16 at 13:17
4

does not work if you have elements in docs that do not have ids in the ordering list – Dan Hunex Jun 16 '17 at 19:07
5

Quite inefficient - IndexOf is being called for every element in the source collection and OrderBy has to order the elements. The solution by @Jodrell is much faster. – sdds Nov 29 '18 at 14:09
6

@DanHunex if you need the non existing ids to appear at the end of the list you can do: .OrderBy(d=> { var index = docIds.IndexOf(d.Id); if (index == -1) index = docIds.Count; return index; }) – nicolascolman Feb 10 '21 at 23:27

Jodrell · Answer 2 · 2022-09-27T08:54:54.483

50

Since you don't specify T,

public static IEnumerable<T> OrderBySequence<T, TId>(
       this IEnumerable<T> source,
       IEnumerable<TId> order,
       Func<T, TId> idSelector)
{
    var lookup = source.ToDictionary(idSelector, t => t);
    foreach (var id in order)
    {
        yield return lookup[id];
    }
}

Is a generic extension for what you want.

You could use the extension like this perhaps,

var orderDocs = docs.OrderBySequence(docIds, doc => doc.Id);

A safer version might be

public static IEnumerable<T> OrderBySequence<T, TId>(
       this IEnumerable<T> source,
       IEnumerable<TId> order,
       Func<T, TId> idSelector)
{
    var lookup = source.ToLookup(idSelector, t => t);
    foreach (var id in order)
    {
        foreach (var t in lookup[id])
        {
           yield return t;
        }
    }
}

which will work if source does not zip exactly with order.

edited Sep 27 '22 at 08:54

answered Mar 07 '13 at 15:53

Jodrell

34,946
5
87
124

1

I used this solution and it worked. Just that, i had to make the method static and the class static. – vinmm May 07 '20 at 06:15
1

10 years old (almost) and still a wonderful solution. tnx (likewise had to embed in a static helper class but does offer great reuse) – jim tollan Apr 22 '22 at 08:21
1

@jimtollan, Nice of you to say so. I guess it is also a good reflection on Stack Overflow. You should bear in mind that `Join` works too. [Sort a list from another list IDs](https://stackoverflow.com/a/55650341) – Jodrell Apr 22 '22 at 11:23
+1 more versatile, e.g : `EmployeeList.OrderBySequence(HospitalList.OrderBy(h => h.Position).Select(h => h.Id), e => e.HospitalId)` gives : employees order by their hospital itself order by its position – Flou Sep 01 '23 at 12:55

Kladzey · Answer 3 · 2019-07-10T17:56:48.083

29

Jodrell's answer is best, but actually he reimplemented System.Linq.Enumerable.Join. Join also uses Lookup and keeps ordering of source.

    docIds.Join(
      docs,
      i => i,
      d => d.Id,
      (i, d) => d);

edited Jul 10 '19 at 17:56

answered Apr 12 '19 at 11:11

Kladzey

411
4
5

1

That is the answer we are looking for – Orace Jan 27 '20 at 13:27
23

This just proves that Join is too difficult to understand since everyone agreed that rewriting it was easier. – PRMan Apr 16 '20 at 21:15

score -4 · Answer 4 · answered Mar 07 '13 at 15:44

-4

One simple approach is to zip with the ordering sequence:

List<T> docs = GetDocsFromDb(...).Zip(docIds, Tuple.Create)
               .OrderBy(x => x.Item2).Select(x => x.Item1).ToList();

answered Mar 07 '13 at 15:44

Albin Sunnanbo

46,430
8
69
108

Because `Zip` combines each index (into a Tuple) with the document in the same position in the corresponding list. Then the OrderBy sorts the Tuples by the index part and then the select digs our just the docs from the now ordered list. – Albin Sunnanbo Mar 07 '13 at 16:58
but, the result of GetDocsFromDb is unordered so you'll be creating Tuples where `Item1` is unrelated to `Item2`. – Jodrell Mar 07 '13 at 17:15
1

I think this will produce incorrect results since ordering performing uppon id and not the index. – Michael Logutov Mar 31 '14 at 13:18

Sort a list from another list IDs

4 Answers4

Linked

Related