Сравнение 2 огромных списков с использованием C# несколько раз (с завихрением)

Question

Привет всем, отличное сообщество, которое вы получили здесь. Я инженер-электрик, делающий некоторые «программирующие» работы на стороне, чтобы помочь оплатить счета. Я говорю это, потому что хочу, чтобы вы учли, что у меня нет надлежащей подготовки компьютерных наук, но я кодировался последние 7 лет.

У меня есть несколько таблиц excel с информацией (все числовые), в основном это «набранные номера телефонов» в одном столбце и количество минут для каждого из этих номеров на другом. Отдельно у меня есть список «кодовых номеров префикса оператора» для разных операторов в моей стране. То, что я хочу сделать, это разделить весь «трафик» на перевозчика. Вот сценарий:

Первый набранный номер строки: 123456789ABCD, 100 < - Это будет 13-значный номер телефона и 100 минут.

У меня есть список 12,000+ префиксов кодов для несущей 1, эти коды имеют разную длину, и мне нужно, чтобы проверить все из них:

Префикс 1: < - этот код составляет 7 цифр.

Мне нужно проверить первые 7 цифр для набранного номера, сравнить его с набранным номером, если совпадение найдено, я бы добавил количество минут для промежуточного итога для последующего использования. Учтите, что не все префиксные коды имеют одинаковую длину, иногда они короче или длиннее.

Большая часть этого должна быть куском пирога, и я мог бы это сделать, но я получаю от страха огромное количество данных; В некоторых случаях списки набранных номеров состоят из 30 000 номеров, а «код префикса несущей» содержит около 13 000 строк, и я обычно проверяю 3 оператора, что означает, что я должен выполнять множество «совпадений».

У кого-нибудь есть идеи, как это сделать эффективно с помощью C#? Или любой другой язык, чтобы быть добрым честным. Мне нужно делать это довольно часто, и разработка инструмента для этого имеет смысл. Мне нужна хорошая перспектива у кого-то, у кого есть этот «компьютерный ученый».

Списки не обязательно должны быть в листах Excel, я могу экспортировать в файл csv и работать оттуда, мне не нужен интерфейс «MS Office».

Благодарим за помощь.

Обновление:

Спасибо всем за ваше время на ответ на мой вопрос. Думаю, по моему невежеству я преувеличиваю слово «эффективный». Я не выполняю эту задачу каждые несколько секунд. Это то, что я должен делать один раз в день, и мне не нравится делать это с помощью Excel и VLOOKUP и т. Д.

Я узнал о новых концепциях от вас, ребята, и я надеюсь, что смогу построить решение (ы), используя ваши идеи ,

Answer 1

UPDATE

Вы можете сделать простой трюк - группа префиксов по их первым цифрам в словарь и соответствуют номерам только против правильного подмножества. Я протестировал его с помощью следующих двух операторов LINQ, предполагая, что каждый префикс имеет как минимум три digis.

const Int32 minimumPrefixLength = 3; 

var groupedPefixes = prefixes 
    .GroupBy(p => p.Substring(0, minimumPrefixLength)) 
    .ToDictionary(g => g.Key, g => g); 

var numberPrefixes = numbers 
    .Select(n => groupedPefixes[n.Substring(0, minimumPrefixLength)] 
     .First(n.StartsWith)) 
    .ToList(); 

Так как быстро это происходит? 15 000 префиксов и 50 000 номеров заняли менее 250 миллисекунд. достаточно быстро для двух строк кода?

Обратите внимание, что производительность сильно зависит от минимальной длины префикса (MPL), следовательно, от количества групп префикса, которые вы можете построить.

 
    MPL Runtime 
    ----------------- 
    1  10.198 ms 
    2  1.179 ms 
    3  205 ms 
    4  130 ms 
    5  107 ms 

Просто для того, чтобы дать приблизительную идею - я сделал всего один проход и у меня было много другого материала.

Оригинальный ответ

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

Я только что сделал тест. Я создал список с 15 000 уникальными префиксами с 5-10 цифрами. Из этих префиксов я сгенерировал 50 000 номеров с префиксом и еще 5-10 цифр.

List<String> prefixes = GeneratePrefixes(); 
List<String> numbers = GenerateNumbers(prefixes); 

Затем я использовал следующий запрос LINQ to Object, чтобы найти префикс каждого номера.

Ну, это заняло около минуты на моем ноутбуке Core 2 Duo с частотой 2,0 ГГц. Поэтому, если одноминутное время обработки приемлемо, возможно, два или три, если вы включите агрегацию, я бы не стал оптимизировать что-либо. Конечно, было бы неплохо, если бы программа могла выполнить задачу за секунду или два, но это добавит немного сложности и многого, чтобы ошибиться. И для разработки, написания и тестирования требуется время. Заявление LINQ заняло только мои секунды.

тестовое приложение

Обратите внимание, что породив множество префиксов очень медленно и может занять минуту или две.

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 
using System.Text; 

namespace Test 
{ 
    static class Program 
    { 
     static void Main() 
     { 
      // Set number of prefixes and calls to not more than 50 to get results 
      // printed to the console. 

      Console.Write("Generating prefixes"); 
      List<String> prefixes = Program.GeneratePrefixes(5, 10, 15); 
      Console.WriteLine(); 

      Console.Write("Generating calls"); 
      List<Call> calls = Program.GenerateCalls(prefixes, 5, 10, 50); 
      Console.WriteLine(); 

      Console.WriteLine("Processing started."); 

      Stopwatch stopwatch = new Stopwatch(); 

      const Int32 minimumPrefixLength = 5; 

      stopwatch.Start(); 

      var groupedPefixes = prefixes 
       .GroupBy(p => p.Substring(0, minimumPrefixLength)) 
       .ToDictionary(g => g.Key, g => g); 

      var result = calls 
       .GroupBy(c => groupedPefixes[c.Number.Substring(0, minimumPrefixLength)] 
        .First(c.Number.StartsWith)) 
       .Select(g => new Call(g.Key, g.Sum(i => i.Duration))) 
       .ToList(); 

      stopwatch.Stop(); 

      Console.WriteLine("Processing finished."); 
      Console.WriteLine(stopwatch.Elapsed); 

      if ((prefixes.Count <= 50) && (calls.Count <= 50)) 
      { 
       Console.WriteLine("Prefixes"); 
       foreach (String prefix in prefixes.OrderBy(p => p)) 
       { 
        Console.WriteLine(String.Format(" prefix={0}", prefix)); 
       } 

       Console.WriteLine("Calls"); 
       foreach (Call call in calls.OrderBy(c => c.Number).ThenBy(c => c.Duration)) 
       { 
        Console.WriteLine(String.Format(" number={0} duration={1}", call.Number, call.Duration)); 
       } 

       Console.WriteLine("Result"); 
       foreach (Call call in result.OrderBy(c => c.Number)) 
       { 
        Console.WriteLine(String.Format(" prefix={0} accumulated duration={1}", call.Number, call.Duration)); 
       } 
      } 

      Console.ReadLine(); 
     } 

     private static List<String> GeneratePrefixes(Int32 minimumLength, Int32 maximumLength, Int32 count) 
     { 
      Random random = new Random(); 
      List<String> prefixes = new List<String>(count); 
      StringBuilder stringBuilder = new StringBuilder(maximumLength); 

      while (prefixes.Count < count) 
      { 
       stringBuilder.Length = 0; 

       for (int i = 0; i < random.Next(minimumLength, maximumLength + 1); i++) 
       { 
        stringBuilder.Append(random.Next(10)); 
       } 

       String prefix = stringBuilder.ToString(); 

       if (prefixes.Count % 1000 == 0) 
       { 
        Console.Write("."); 
       } 

       if (prefixes.All(p => !p.StartsWith(prefix) && !prefix.StartsWith(p))) 
       { 
        prefixes.Add(stringBuilder.ToString()); 
       } 
      } 

      return prefixes; 
     } 

     private static List<Call> GenerateCalls(List<String> prefixes, Int32 minimumLength, Int32 maximumLength, Int32 count) 
     { 
      Random random = new Random(); 
      List<Call> calls = new List<Call>(count); 
      StringBuilder stringBuilder = new StringBuilder(); 

      while (calls.Count < count) 
      { 
       stringBuilder.Length = 0; 

       stringBuilder.Append(prefixes[random.Next(prefixes.Count)]); 

       for (int i = 0; i < random.Next(minimumLength, maximumLength + 1); i++) 
       { 
        stringBuilder.Append(random.Next(10)); 
       } 

       if (calls.Count % 1000 == 0) 
       { 
        Console.Write("."); 
       } 

       calls.Add(new Call(stringBuilder.ToString(), random.Next(1000))); 
      } 

      return calls; 
     } 

     private class Call 
     { 
      public Call (String number, Decimal duration) 
      { 
       this.Number = number; 
       this.Duration = duration; 
      } 

      public String Number { get; private set; } 
      public Decimal Duration { get; private set; } 
     } 
    } 
} 

Answer 2

Возможно, было бы проще (не обязательно более эффективно) делать это в базе данных вместо C#.

Вы можете вставить строки в базу данных, а вставить определить носитель и включить его в запись (возможно, в триггер вставки).

Тогда ваш отчет будет представлять собой запрос суммы на таблицу.

Answer 3

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

Затем создайте словарь от несущей до int или long (всего).

Затем для каждого набранного номера, просто выполните свой путь вниз по три, пока не найдете перевозчика. Найдите общее количество минут для носителя и добавьте текущую строку - затем перейдите.

Answer 4

Простейшая структура данных, которая сделает это достаточно эффективно, будет списком множеств. Сделайте набор для каждой несущей, содержащий все префиксы.

Теперь, чтобы связать вызов с носителем:

foreach (Carrier carrier in carriers) 
{ 
    bool found = false; 

    for (int length = 1; length <= 7; length++) 
    { 
     int prefix = ExtractDigits(callNumber, length); 

     if (carrier.Prefixes.Contains(prefix)) 
     { 
      carrier.Calls.Add(callNumber); 
      found = true; 
      break; 
     } 
    } 

    if (found) 
     break; 
} 

Если у вас есть 10 носителей, будет 70 просмотры в наборе на один вызов. Но поиск в наборе не слишком медленный (намного быстрее, чем линейный поиск). Таким образом, это должно дать вам довольно большую скорость по линейному поиску грубой силы.

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

Answer 5

Я бы, скорее всего, просто поместил записи в список, отсортировал его, а затем использовал binary search для поиска совпадений. Определите критерии соответствия бинарного поиска, чтобы вернуть первый элемент, который соответствует, затем перебирайте по списку, пока не найдете тот, который не соответствует. Бинарный поиск занимает всего около 15 сравнений для поиска списка из 30 000 предметов.

Answer 6

Возможно, вы захотите использовать HashTable в C#.

Таким образом, у вас есть пары с ключом, а вашими ключами могут быть номера телефонов, а ваше значение - общие минуты. Если в наборе ключей найдено совпадение, измените общие минуты, иначе добавьте новый ключ.

Вам тогда просто нужно изменить алгоритм поиска, чтобы не смотреть на весь ключ, а только на первые 7 цифр.

Answer 7

Как сбрасывать данные в пару таблиц базы данных, а затем запрашивать их с помощью SQL? Легко!

CREATE TABLE dbo.dialled_numbers (number VARCHAR(100), minutes INT) 

CREATE TABLE dbo.prefixes (prefix VARCHAR(100)) 

-- now populate the tables, create indexes etc 
-- and then just run your query... 

SELECT p.prefix, 
    SUM(n.minutes) AS total_minutes 
FROM dbo.dialled_numbers AS n 
    INNER JOIN dbo.prefixes AS p 
     ON n.number LIKE p.prefix + '%' 
GROUP BY p.prefix 

(Это было написано для SQL Server, но должно быть очень просто перевести для другой СУБД.)