Нужна помощь по алгоритму

Question

Мне нужна помощь по алгоритму. Я произвольно сгенерировал числа с 6 цифрами. Подобно;

Есть около 1 миллиона из них сохраняются в файле построчно. Я должен отфильтровать их в соответствии с правилом, которое я пытаюсь описать ниже.

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

Наш номер: 123456 Увеличьте первую цифру на 1, и число станет следующим: 223456. Удалите все файлы 223456 из файла. Увеличьте вторую цифру на 1, число станет: 133456. Удалите все 133456s из файла и т. Д.

Я могу сделать это, как я опишу, но мне нужно, чтобы это было «FAST».

Так может ли кто-нибудь мне помочь в этом?

Спасибо.

Answer 1

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

public static IEnumerable<int> FilterInts(IEnumerable<int> ints) 
    { 
     var removed = new HashSet<int>(); 

     foreach (var i in ints) 
     { 
      var iStr = i.ToString("000000").ToCharArray(); 

      for (int j = 0; j < iStr.Length; j++) 
      { 
       var c = iStr[j]; 

       if (c == '9') 
        iStr[j] = '0'; 
       else 
        iStr[j] = (char)(c + 1); 

       removed.Add(int.Parse(new string(iStr))); 

       iStr[j] = c; 
      } 

      if (!removed.Contains(i)) 
       yield return i; 
     } 
    } 

Вы можете использовать этот метод для создания IEnumerable<int> из файла:

public static IEnumerable<int> ReadIntsFrom(string path) 
    { 
     using (var reader = File.OpenText(path)) 
     { 
      string line; 
      while ((line = reader.ReadLine()) != null) 
       yield return int.Parse(line); 
     } 
    } 

Answer 2

Для начала я просто прочитал все числа в массиве.

Когда вы, наконец, закончите, перепишите файл.

Answer 3

Возьмите все числа из файла на ArrayList, а затем:

взять число потоков, как количество цифр

приращению первая цифра на число в первом потоке, второй во втором нить, а затем сравнить его с остальными номерами,

было бы быстро, как она будет проходить по параллельной обработке ...

Answer 4

Похоже, что правила вы описываете для целевого числа abdcef вас хочу найти ll, которые содержат a + 1, b + 1, c + 1, d + 1, e + 1 или f + 1 в соответствующем месте. Вы можете сделать это в O (n), перейдя по строкам в файле и сравнивая каждую из шести цифр с цифрой целевого номера, если никакие цифры не совпадают, напишите номер в выходной файл.

Answer 5

Прежде всего, поскольку он составляет около 1 миллиона, вам лучше выполнить алгоритм в ОЗУ, а не на диске, то есть сначала загрузить содержимое в массив, а затем изменить массив, а затем вставить результаты обратно в файл ,

Я бы предложил следующий алгоритм - простой. Предварительно расчитайте все целевые номера, в данном случае 223456, 133456, 124456, 123556, 123466, 123457. Теперь передайте массив, и если число не является ни одним из них, напишите его в другой массив. В качестве альтернативы, если это один из этих номеров, удалите его (рекомендуется, если ваша структура данных имеет O (1) удалить)

Answer 6

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

Мне бы пришлось вдаваться в него дальше, но я бы также, вероятно, использовал словарь для нелинейных поисков, если вы сравниваете числа, которые не находятся в последовательности.

Answer 7

Прочитайте все свои номера из файла и сохраните их на карте, где номер является ключом, а логическое значение - это значение, означающее, что это значение не было удалено. (Истина существует, ложные средства удаляются).

Затем итерации через ваши ключи. Для каждого ключа установите для карты значение false для значений, которые вы удаляете из списка.

Идите в свой список еще раз и получите все ключи, где значение истинно. Это список оставшихся номеров.

public List<int> FilterNumbers(string fileName) 
{ 
    StreamReader sr = File.OpenTest(fileName); 
    string s = ""; 
    Dictionary<int, bool> numbers = new Dictionary<int, bool>(); 
    while((s = sr.ReadLine()) != null) 
    { 
     int number = Int32.Parse(s); 
     numbers.Add(number,true); 
    } 
    foreach(int number in numbers.Keys) 
    { 
     if(numbers[number]) 
     { 
      if(numbers.ContainsKey(100000+number)) 
       numbers[100000+number]=false; 
      if(numbers.ContainsKey(10000+number)) 
       numbers[10000+number]=false; 
      if(numbers.ContainsKey(1000+number)) 
       numbers[1000+number]=false; 
      if(numbers.ContainsKey(100+number)) 
       numbers[100+number]=false; 
      if(numbers.ContainsKey(10+number)) 
       numbers[10+number]=false; 
      if(numbers.ContainsKey(1+number)) 
       numbers[1+number]=false; 
     } 
    } 

    List<int> validNumbers = new List<int>(); 
    foreach(int number in numbers.Keys) 
    { 
     validNumbers.Add(number); 
    } 
    return validNumbers; 
} 

Это может потребоваться проверить, как я не имею C# компилятор на этом компьютере, и я немного ржавый. Алгоритм займет бит бит памяти, который будет выполняться в линейном времени.

** РЕДАКТИРОВАТЬ ** Это приводит к проблемам, когда одно из чисел равно 9. Я обновлю код позже.

Answer 8

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

Начните с идеей @Armen Tsirunyan в:

предвычислять все целевые номера, в этом случае 223456, 133456, 124456, 123556 , 123466, 123457.

Но вместо одного сравните, сделайте это в строку:

string arg = "223456 133456 124456 123556 123466 123457"; 

Затем прочитайте ввод (либо из файла или в памяти). Псевдокод:

foreach (string s in theBigListOfNumbers) 
    if (arg.indexOf(s) == -1) 
     print s; 

Это только одно сравнение в строке ввода, без каких-либо словарей, карт, итераторы и т.д.

Edited добавить:

В набор процессоров команд x86 (а не только Intel), поиск подстроки примерно очень быстро. Например, для поиска символа внутри строки, это всего лишь одна машинная инструкция.

Я должен попросить других взвесить на альтернативных архитектурах.

Answer 9

Как насчет этого. Вы обрабатываете номера один за другим. Номера будут храниться в хэш-таблицах NumbersOK и NumbersNotOK.

1. Возьмите один номер
2. Если это не NumbersNotOK поместить его в хэш NumbersOK
3. Получить это отклонения приращений единственное число в хэш - NumbersNotOK.
4. Удалить все из NumbersOK участников, если они соответствуют каким-либо отклонениям.
5. Повторите с 1 до конца файла
6. Сохраните NumbersOK в файл.

Таким образом, вы пройдете список только один раз. Хэш-таблица составлена ​​именно для таких целей, и это будет очень быстро (нет дорогостоящих методов сравнения).

Этот алгоритм не в полной мере, так как она не работает, когда есть некоторые числа повторяющихся, но может быть обработан с некоторой настройкой ...

Answer 10

Тем не менее звучит как домашнее задание вопрос ... самые быстрые сортировка по миллиону чисел будет n log (n), которая равна 1000000log (1000000), которая равна 6 * 1000000, что совпадает с сопоставлением 6 чисел с каждым из миллионов чисел. Поэтому прямое сравнение будет быстрее, чем сортировка и удаление, потому что после сортировки вам все равно придется сравнивать с удалением. Если, конечно, мои расчеты полностью пропустили цель.

Что-то еще приходит на ум. Когда вы подберете номер, прочитайте его как hex, а не base 10. тогда, возможно, некоторые поразрядные операторы могут как-то помочь. Все еще думая о том, что можно сделать с помощью этого. Будет ли обновляться, если он работает

EDIT: в настоящее время мышление на линиях серого кода. 123456 (наш исходный номер) и 223456 или 133456 будут отключены только на одну цифру, а конвертер с серым кодом быстро поймает его. Здесь поздно ночью, поэтому, если кто-то найдет это полезным и может дать решение ...