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

Question

Мне нужна помощь по алгоритму.Я случайно сгенерировал номера с 6 цифрами.Как;

123654 109431

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

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

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

Я могу сделать это так, как я описываю, но мне нужно, чтобы это было "БЫСТРО".

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

Спасибо.

Answer 1

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

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

Answer 2

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

Начните с идеи @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;

Это только одно сравнение на строку ввода, без словарей, карт, итераторов и т. Д.

Отредактировано, чтобы добавить:

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

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

Answer 3

Этот алгоритм будет хранить много чисел в памяти, но он будет обрабатывать файл по одному номеру за раз, так что вам на самом деле не нужно читать все сразу.Вам нужно только указать 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 4

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

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

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

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

Answer 5

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

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

РЕДАКТИРОВАТЬ: в настоящее время размышления о линиях серого кода. 123456 (наш оригинальный номер) и 223456 или 133456 будут отключены только одной цифрой, и серый кодовый преобразователь быстро их поймает. Здесь поздняя ночь, так что если кто-то найдет это полезным и может дать решение ...

Answer 6

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

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

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

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

Answer 7

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

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

Еще раз переберите свой список и получите все ключи, для которых значение равно true.Это список оставшихся чисел.

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

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

Answer 9

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

Answer 10

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

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