Эффективный способ сортировки строки списка по порядку, определенному в массиве?

Question

Я пытаюсь отсортировать список строк по порядку, определенному в другом массиве. Я знаю, что это возможно разными способами, но я не уверен, как это сделать эффективно. Мне нужно это, чтобы иметь возможность обрабатывать большой несортированный список с тысячами элементов. Вот что я придумал:

List<string> sortStringListByArray(List<string> unsortedList, string[] order)
{
     List<string> sortedList = new List<string>();
     for(int i = 0; i < order.Length; i++)
     {
          foreach(string s in unsortedList)
          {
              if(s.Equals(order[i]))
              {
                  sortedList.Add(s);
              }
          }
     }
     return sortedList;
}

Работает как положено, но определенно не эффективно. Есть ли способ, которым я могу сделать это, не повторяя и список, и порядок?

Редактировать: Уточнение

Спасибо!

Answer 1

Самый простой способ представить это с помощью правого внутреннего соединения:

return order.Join(unsortedList, a => a, b => b, (a, b) => b).ToList();

---

Наилучшая временная сложность - O (n + m) с использованием поиска или словаря:

var lookup = unsortedList.ToLookup(x => x);

return order.SelectMany(x => lookup[x]).ToList();

Вышеприведенное может быть в несколько раз быстрее, если использовать Dictionary<string, int> для получения количества элементов в unsortedList, а затем выполнить цикл по order для получения результата на основе соответствующих значений в словаре счетчиков.

---

Lookup и Dictionary используют хеш-таблицу для хранения значений. Чтобы найти элемент в хеш-таблице, значение хеша вычисляется из значения, которое аналогично предполагаемому местоположению / индексу, где значение находится в хеш-таблице. Это позволяет только 1 или несколько сравнений, необходимых для нахождения (или нет) значения в хеш-таблице. Итак, O (n) для генерации Lookup или Dictionary из unsortedList, и поскольку хеш-таблица имеет среднее время O (1) поиска, только O (m) время, необходимое для генерации результата с использованием Lookup или Dictionary, в результате чего получается общее O (n + m) временная сложность.

Answer 2

Опираясь на ответ @ Ашкана, вы можете сделать order.Distinct().ToList(), который удаляет дубликаты.Поскольку заказ уже отсортирован, вы можете просто обработать его и вернуть.

Answer 3

Вы можете использовать эффективный алгоритм сортировки, используя индекс массива в качестве входных данных для упорядочения.Это было бы более эффективно, чем ваш пример решения.

Например,

List<string> sortStringListByArray(List<string> unsortedList, string[] order)
{
    var orders = new Dictionary<string, int>();

    for (var i = 0; i < order.Length; i++)
        orders[order[i]] = i;

     return unsortedList
         .OrderBy(s => orders[s])
         .ToList();
}

Answer 4

Учитывая ваши комментарии, вы можете просто отсортировать список по его индексу в массиве order:

 List<string> sortedList = unsortedList.OrderBy(x => Array.IndexOf(order, x));