none
Работа с большим объемом данных (чтение файла большого размера с ограничением по ОЗУ) RRS feed

  • Вопрос

  • Имеется текстовый файл, каждая строка которого – произвольное 4-байтное целое число. Всего в файле может быть 1 000 000 000 строк, числа могут повторяться. На машине установлен 1 Гб памяти (ОЗУ). Необходимо вывести все числа, которых в файле нет (задачу упростил - главное понять суть решения проблемы). Язык C#...

    Спасибо за любой совет!


    the victory loves diligens


    • Изменено roma-samojlenko 10 августа 2012 г. 22:11 исправил
    10 августа 2012 г. 22:06

Ответы

  • На ум приходит такой вариант, заведите массив байтов размером Int32.Max / 8 (в восемь раз меньше чем у вас чисел для проверки), это будет 536870912. Если такой массив составить не получится, то можно завести 4 массива. Таким образом, у вас для каждого числа из диапазона в этом массиве будет бит. Дальше, считывая число, находите его бит в массиве и меняете на 1. Как только файл закончился, все индексы битов которые имеют значение 0, будут искомые числа.

    • Помечено в качестве ответа Abolmasov Dmitry 20 августа 2012 г. 7:03
    14 августа 2012 г. 6:43
    Отвечающий
  • Для работы с большими объёмами данных, превышающими имеющийся размер ОЗУ, можно использовать MemoryMappedFile.
    • Помечено в качестве ответа Abolmasov Dmitry 20 августа 2012 г. 7:04
    16 августа 2012 г. 16:33
  • Ну во-первых читать файл потоком, по одному числу за шаг. В сохранении только уникальных чисел я вижу решение проблемы в использовании List. Первый способ - учет существующих чисел при добавлении

    //В начале функции, до считывания
    List<int32> Uniq = new List<int32>(); int have; // после того, как считали четырехбайтовое число из файла, допустим, в переменную NewInt (в цикле считывания) have=0; foreach (int item in Uniq) { if (item == NewInt) { have = 1; break; } } if (have == 0) { Uniq.Add(NewInt); }

    Второй способ - удаление повторений после полного считывания:

    Просто после считанного числа делать

    Uniq.Add(NewInt);

    А потом, имея полный список, можно воспользоваться ответом из темы "Как удалить все одинаковые числа". Чтобы отсортировать числа в списке, нужно вызвать функцию

    Uniq.Sort();

    В результате в списке Uniq у вас будут только уникальные числа. Перебор всех чисел списка приведен в коде, обращатся к конкретному элементу можно как и в массиве, то есть Uniq[3] - третий элемент в списке чисел.


    Drazd






    • Изменено Drazd 15 августа 2012 г. 9:05
    • Помечено в качестве ответа Abolmasov Dmitry 20 августа 2012 г. 7:04
    15 августа 2012 г. 8:14

Все ответы

  • А что значит нет? Если я Вас правильно понял то: всего целых чисел в 4 байта - 4294967296, у Вас в файле может быть 1 000 000 000, т.е остаётся около 3 200 000 000 (или больше, т.к. числа повторяются), их и надо вывести?
    11 августа 2012 г. 11:13
    Модератор
  • Абсолютно верно - данные(целые числа) могут повторяться, надо пройтись по имеющимся числам в файле (огромного размера), и выводить отсутствующие в процессе прохождения числа...Главное ограничение ОЗУ 1 Гб...Моя задумка состоит в том, что необходимо произвести сортировку необычным способом (все-таки учитывая объем данных времени этот процесс может занять очень много), после чего просто инкрементно пройтись по отсортированному массиву и попутно выводить число, которое НЕ встретилось в отсортированном списке. Но не факт, что моя идея правильна (с учетом ограничения на память).

    the victory loves diligens

    11 августа 2012 г. 17:00
  • Если я прав то у вас все равно не хватит места для создания такого массива в памяти (1 гиг)

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

    14 августа 2012 г. 5:33
  • На ум приходит такой вариант, заведите массив байтов размером Int32.Max / 8 (в восемь раз меньше чем у вас чисел для проверки), это будет 536870912. Если такой массив составить не получится, то можно завести 4 массива. Таким образом, у вас для каждого числа из диапазона в этом массиве будет бит. Дальше, считывая число, находите его бит в массиве и меняете на 1. Как только файл закончился, все индексы битов которые имеют значение 0, будут искомые числа.

    • Помечено в качестве ответа Abolmasov Dmitry 20 августа 2012 г. 7:03
    14 августа 2012 г. 6:43
    Отвечающий
  • Интересный вариант, можно краткий код для лучшего понятия предложенного метода? Не совсем понял..

    the victory loves diligens

    14 августа 2012 г. 13:46
  • Ну во-первых читать файл потоком, по одному числу за шаг. В сохранении только уникальных чисел я вижу решение проблемы в использовании List. Первый способ - учет существующих чисел при добавлении

    //В начале функции, до считывания
    List<int32> Uniq = new List<int32>(); int have; // после того, как считали четырехбайтовое число из файла, допустим, в переменную NewInt (в цикле считывания) have=0; foreach (int item in Uniq) { if (item == NewInt) { have = 1; break; } } if (have == 0) { Uniq.Add(NewInt); }

    Второй способ - удаление повторений после полного считывания:

    Просто после считанного числа делать

    Uniq.Add(NewInt);

    А потом, имея полный список, можно воспользоваться ответом из темы "Как удалить все одинаковые числа". Чтобы отсортировать числа в списке, нужно вызвать функцию

    Uniq.Sort();

    В результате в списке Uniq у вас будут только уникальные числа. Перебор всех чисел списка приведен в коде, обращатся к конкретному элементу можно как и в массиве, то есть Uniq[3] - третий элемент в списке чисел.


    Drazd






    • Изменено Drazd 15 августа 2012 г. 9:05
    • Помечено в качестве ответа Abolmasov Dmitry 20 августа 2012 г. 7:04
    15 августа 2012 г. 8:14
  • Для работы с большими объёмами данных, превышающими имеющийся размер ОЗУ, можно использовать MemoryMappedFile.
    • Помечено в качестве ответа Abolmasov Dmitry 20 августа 2012 г. 7:04
    16 августа 2012 г. 16:33
  • Не забывайте отмечать ответы. Спасибо


    Для связи [mail]

    20 августа 2012 г. 7:04