Как сопоставить 2 списка наиболее эффективно (быстро)?

Question

У меня 2 lists<string> предметов, источник и цель. Элементы в исходном списке будут иметь от 0 до n совпадений в целевом списке, но повторных совпадений не будет.

Учитывая, что оба списка отсортированы, как бы вы сделали сравнение наиболее эффективно с точки зрения производительности.

Пример:

source = {"1", "2", "A", "B", ...}
target = {"1 - new music", "1 / classic", "1 | pop", "2 edit", "2 no edit", "A - sing", "B (listen)", ...}

По сути, это простое совпадение префиксов, но, скажем, у вас есть метод с именем MatchName. Вы можете использовать новую функцию, если хотите выполнять более оптимизированный поиск. NameMatch просто сравнивает 2 строки и возвращает bool.

В конце у источника [0] будет источник [0]. В этом случае соответствия содержат цели [0, 1 и 2].

Answer 1

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

Без сопоставленных элементов в цели

При условии, что списки отсортированы, и в target нет элементов, которые не могут быть сопоставлены с source:

static List<string>[] FindMatches(string[] source, string[] target)
{
    // Initialize array to hold results
    List<string>[] matches = new List<string>[source.Length];
    for (int i = 0; i < matches.Length; i++)
        matches[i] = new List<string>();

    int s = 0;
    for (int t = 0; t < target.Length; t++)
    {
        while (!MatchName(source[s], target[t]))
        {
            s++;
            if (s >= source.Length)
                return matches;
        }

        matches[s].Add(target[t]);
    }

    return matches;
}

С непревзойденными элементами

Если существует вероятность того, что элементы, существующие в target, не будут совпадать с source, вышеприведенное будет нарушено (если элементы не находятся в конце цели). Чтобы исправить это, было бы лучше пойти с другой реализацией для сравнения. Вместо логического значения нам нужно, чтобы он возвращал «меньше чем», «равно» или «больше чем», как Comparer при использовании в сортировке:

static List<string>[] FindMatches(string[] source, string[] target)
{
    // Initialize array to hold results
    List<string>[] matches = new List<string>[source.Length];
    for (int i = 0; i < matches.Length; i++)
        matches[i] = new List<string>();

    int s = 0;
    for (int t = 0; t < target.Length; t++)
    {
        int m = CompareName(source[s], target[t]);
        if (m == 0)
        {
            matches[s].Add(target[t]);
        }
        else if (m > 0)
        {
            s++;
            if (s >= source.Length)
                return matches;
            t--;
        }
    }

    return matches;
}

static int CompareName(string source, string target)
{
    // Whatever comparison you need here, this one is really basic :)
    return target[0] - source[0];
}

В остальном они в основном одинаковы. Как видите, вы перебираете целевые элементы один раз, продвигая индекс к исходному массиву, когда вы больше не находите совпадения.

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

Опять же, первый алгоритм занимает 0,18 секунды с 1 миллионом целевых элементов на моей машине в режиме отладки. Второй еще быстрее ( 0,03 секунды ), но это из-за более простого сравнения, которое делается. Возможно, вам придется сравнивать все до первого символа пробела, делая его значительно медленнее.

Answer 2

Поскольку они отсортированы, разве это не просто O (N) цикл слияния?

ia = ib = 0;
while(ia < na && ib < nb){
  if (A[ia] < B[ib]){
    // A[ia] is unmatched
    ia++;
  }
  else if (B[ib] < A[ia]){
    // B[ib] is unmatched
    ib++;
  }
  else {
    // A[ia] matches B[ib]
    ia++;
    ib++;
  }
}
while(ia < na){
  // A[ia] is unmatched
  ia++;
}
while(ib < nb){
  // B[ib] is unmatched
  ib++;
}

Answer 3

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

Как говорится, мне нужно что-то сделать с моей чашкой кофе, так что вот, пожалуйста. Одним из преимуществ приведенного ниже является то, что он разрешает вещи в списке целей, которые не имеют совпадений в списке источников, хотя я не уверен, что вам потребуется эта функциональность.

class Program
{
    public class Source
    {
        private readonly string key;
        public string Key { get { return key;}}

        private readonly List<string> matches = new List<string>();
        public List<string> Matches { get { return matches;} }

        public Source(string key)
        {
            this.key = key;
        }
    }

    static void Main(string[] args)
    {
        var sources = new List<Source> {new Source("A"), new Source("C"), new Source("D")};
        var targets = new List<string> { "A1", "A2", "B1", "C1", "C2", "C3", "D1", "D2", "D3", "E1" };

        var ixSource = 0;
        var currentSource = sources[ixSource++];

        foreach (var target in targets)
        {
            var compare = CompareSourceAndTarget(currentSource, target);

            if (compare > 0)
                continue;

            // Try and increment the source till we have one that matches 
            if (compare < 0)
            {
                while ((ixSource < sources.Count) && (compare < 0))
                {
                    currentSource = sources[ixSource++];
                    compare = CompareSourceAndTarget(currentSource, target);
                }
            }

            if (compare == 0)
            {
                currentSource.Matches.Add(target);
            }

            // no more sources to match against
            if ((ixSource > sources.Count))
                break;
        }

        foreach (var source in sources)
        {
            Console.WriteLine("source {0} had matches {1}", source.Key, String.Join(" ", source.Matches.ToArray()));
        }
    }

    private static int CompareSourceAndTarget(Source source, string target)
    {
        return String.Compare(source.Key, target.Substring(0, source.Key.Length), StringComparison.OrdinalIgnoreCase);
    }
}

Answer 4

Поскольку элементы отсортированы, вы можете просто зациклить списки:

string[] source = {"1", "2", "A", "B" };
string[] target = { "1 - new music", "1 / classic", "1 | pop", "2 edit", "2 no edit", "A - sing", "B (listen)" };

List<string>[] matches = new List<string>[source.Length];
int targetIdx = 0;
for (int sourceIdx = 0; sourceIdx < source.Length; sourceIdx++) {
   matches[sourceIdx] = new List<string>();
   while (targetIdx < target.Length && NameMatch(source[sourceIdx], target[targetIdx])) {
      matches[sourceIdx].Add(target[targetIdx]);
      targetIdx++;
   }
}

Answer 5

Отредактировано, переписано, не проверено, должно иметь производительность O (источник + цель). Использование может быть MatchMaker.Match (источник, цель) .ToList ();

public static class MatchMaker
{
    public class Source
    {
        char Term { get; set; }
        IEnumerable<string> Results { get; set; }
    }

    public static IEnumerable<Source> Match(IEnumerable<string> source, IEnumerable<string> target)
    {
        int currentIndex = 0;
        var matches = from term in source
                      select new Source
                      {
                          Term = term[0],
                          Result = from result in target.FromIndex(currentIndex)
                                       .TakeWhile((r, i) => {
                                           currentIndex = i;
                                           return r[0] == term[0];
                                       })
                                   select result
                      };
    }
    public static IEnumerable<T> FromIndex<T>(this IList<T> subject, int index)
    {
        while (index < subject.Count) {
            yield return subject[index++];
        }
    }
}

---

Простой LinQ, вероятно, не самый быстрый, но самый ясный:

var matches = from result in target
              from term in source
              where result[0] == term[0]
              select new {
              Term: term,
              Result: result
              };

Я против преждевременной оптимизации.

Answer 6

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

Answer 7

Я думаю, что лучшим способом было бы подготовить индекс. Как это (Javascript)

index = [];
index["1"] = [0,1,2];
index["2"] = [3,4];

Хорошо отсортированные списки в этом случае на самом деле не требуются.