Удаление повторяющихся элементов из файла

@ArmanPrestige · Регистрация: 15.01.2013

Author24 — интернет-сервис помощи студентам

Доброго. Имеется файл, в котором записаны строки (это числа, которые поместятся в 4 байта). В теории, строк в файле может быть столько, сколько хватит места на диске.
Необходимо обработать этот файл и записать в новый файл без повторений. То есть если на входе

Код

То на выходе должо получится

Код

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

Кто что предложит?

@Mikhail1990 · 29.12.2016, 17:16

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

@ArmanPrestige · 29.12.2016, 18:07 **[ТС]**

Mikhail1990, проблема в том, что мне не хватит ОЗУ

@kamre · 29.12.2016, 18:57

Сообщение от ArmanPrestige

проблема в том, что мне не хватит ОЗУ

Раз "числа, которые поместятся в 4 байта", то их всего 2^32, и нужно 2^32 бит для хранения флагов под каждой число. А это уже умещается в 2^29 байт, т.е. в 512Мб.

@Mikhail1990 · 29.12.2016, 19:02

ArmanPrestige, так не считывайте все сразу, а по куску и выгружайте готовое в файл. Или напрямую с файлом работать.

@ArmanPrestige · 29.12.2016, 19:28 **[ТС]**

Сообщение от kamre

нужно 2^32 бит для хранения флагов под каждой число

Хранение флагов понятно, но мне же не только флаги хранить надо, а и сами числа тоже, самый худший случай (если все числа в допустимом диапазоне есть в файле) потребует 2^32 * 4 байт (16 гб.)

Сообщение от kamre

А это уже умещается в 2^29 байт, т.е. в 512Мб.

не совсем понял, откуда взялась 29 степепень?

Добавлено через 3 минуты
Mikhail1990, допустим 9гб файл, обработаю я его кусками по 1гб. Где гарантия, что нету повторений между куском №1 и, например, кусками №2 и №7?

@Mikhail1990 · 29.12.2016, 19:34

ArmanPrestige, да согласен. Тогда сразу в файле меняйте.

@ArmanPrestige · 29.12.2016, 19:37 **[ТС]**

Mikhail1990, что сразу менять?

Хотелось бы конкретики, мне нужен более точный алгоритм

@Mikhail1990 · 29.12.2016, 19:48

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

@ArmanPrestige · 29.12.2016, 19:54 **[ТС]**

Mikhail1990, буду изучать, потом отпишусь, спасибо.

@kamre · 29.12.2016, 20:41

Сообщение от ArmanPrestige

Хранение флагов понятно, но мне же не только флаги хранить надо, а и сами числа тоже

Не нужно хранить сами числа, т.к. "на выходе порядок необязательно сохранять". Просто пройтись по всем 2^32 флагам и записать по порядку те числа, для которых установлен флаг.

Сообщение от ArmanPrestige

откуда взялась 29 степепень?

2^32 бит = 2^32/8 байт = 2^32/2^3 = 2^(32 - 3) = 2^29

@Nemovok · 29.12.2016, 22:33

А что если так: ?

C++

while (файл не закончился) { 
  for (size_t i = 0; i < 256 && std::getline(file, str); i++) {
    Тут игнорировать обработанное количество строк, изначально пусть 0
    strBackup = strBackup + '.' + str; 
  }
  Убрать из strBackup повторения.
  strResult += strBackup;
}

@ArmanPrestige · 30.12.2016, 00:22 **[ТС]**

Сообщение от kamre

2^32 бит = 2^32/8 байт = 2^32/2^3 = 2^(32 - 3) = 2^29

Я верно понимаю, что вы имеете в виду использование битовых полей?

@kamre · 30.12.2016, 12:18

Сообщение от ArmanPrestige

Я верно понимаю, что вы имеете в виду использование битовых полей?

Не верно, достаточно использовать std::vector<bool>.

@ArmanPrestige · 30.12.2016, 12:37 **[ТС]**

kamre, зачем вектор? лучше уже std::bitset

@trdm · 30.12.2016, 16:53

Можно еще попробовать хранить структуры с диапазонами в виде мин/макс.
Надо подумать

@alexu_007 · 01.01.2017, 16:53

По моему - решение очевидное. Памяти нужно будет 2^32 бит. Читаешь из исходного файла 1-е число, устанавливаешь соотв. числу бит (номер которого в списке равен номеру числа) в true, скидываешь число в файл-приёмник, читаешь следующее, проверяешь бит, если true - число уже было, пропускаешь, если false - число раньше не встречалось, бит в true и число в файл-приёмник. И так далее до конца файла.

Т.к. чисел разных 4-х битных всего 2^32, то и длина файла приёмника не может быть больше этого значения: каждой цифры по 1 штуке. Собсна, когда все цифры будут в файле приёмнике - дальше продолжать не имеет смысла.

@Skjame · 02.01.2017, 18:50

alexu_007, с точки зрения экономии памяти - хорошо. Но ББ в отличии от микроконтроллеров не очень любит с битами работать. Так что я бы в список складывал и проверял его на

C++ (Qt)

1	bool QList::contains(const T& val)

@ArmanPrestige Pied Piper 236 / 227 / 57 Регистрация: 15.01.2013 Сообщений: 855
	29.12.2016, 19:54 [ТС]	10
	Mikhail1990, буду изучать, потом отпишусь, спасибо. 0

@kamre 127 / 131 / 11 Регистрация: 25.12.2011 Сообщений: 443
	29.12.2016, 20:41	11
	Сообщение от ArmanPrestige Хранение флагов понятно, но мне же не только флаги хранить надо, а и сами числа тоже Не нужно хранить сами числа, т.к. "на выходе порядок необязательно сохранять". Просто пройтись по всем 2^32 флагам и записать по порядку те числа, для которых установлен флаг. Сообщение от ArmanPrestige откуда взялась 29 степепень? 2^32 бит = 2^32/8 байт = 2^32/2^3 = 2^(32 - 3) = 2^29 0

@kamre 127 / 131 / 11 Регистрация: 25.12.2011 Сообщений: 443
	30.12.2016, 12:18	14
	Сообщение от ArmanPrestige Я верно понимаю, что вы имеете в виду использование битовых полей? Не верно, достаточно использовать std::vector<bool>. 0

@Mikhail1990 27 / 26 / 6 Регистрация: 22.03.2014 Сообщений: 277
	29.12.2016, 17:16	2
	Так, а что тут сложного считывайте по одной строке, новое слово добавляйте в map слово и значение. Потом проверяйте ищите если слово уже есть то пропускаем и идем дальше. А лучше сразу диапазон строк так быстрее будет. 0

@ArmanPrestige Pied Piper 236 / 227 / 57 Регистрация: 15.01.2013 Сообщений: 855
	29.12.2016, 18:07 [ТС]	3
	Mikhail1990, проблема в том, что мне не хватит ОЗУ 0

@kamre 127 / 131 / 11 Регистрация: 25.12.2011 Сообщений: 443
	29.12.2016, 18:57	4
	Сообщение от ArmanPrestige проблема в том, что мне не хватит ОЗУ Раз "числа, которые поместятся в 4 байта", то их всего 2^32, и нужно 2^32 бит для хранения флагов под каждой число. А это уже умещается в 2^29 байт, т.е. в 512Мб. 0

@Mikhail1990 27 / 26 / 6 Регистрация: 22.03.2014 Сообщений: 277
	29.12.2016, 19:02	5
	ArmanPrestige, так не считывайте все сразу, а по куску и выгружайте готовое в файл. Или напрямую с файлом работать. 0

@ArmanPrestige Pied Piper 236 / 227 / 57 Регистрация: 15.01.2013 Сообщений: 855
	29.12.2016, 19:28 [ТС]	6
	Сообщение от kamre нужно 2^32 бит для хранения флагов под каждой число Хранение флагов понятно, но мне же не только флаги хранить надо, а и сами числа тоже, самый худший случай (если все числа в допустимом диапазоне есть в файле) потребует 2^32 * 4 байт (16 гб.) Сообщение от kamre А это уже умещается в 2^29 байт, т.е. в 512Мб. не совсем понял, откуда взялась 29 степепень? Добавлено через 3 минуты Mikhail1990, допустим 9гб файл, обработаю я его кусками по 1гб. Где гарантия, что нету повторений между куском №1 и, например, кусками №2 и №7? 0

@Mikhail1990 27 / 26 / 6 Регистрация: 22.03.2014 Сообщений: 277
	29.12.2016, 19:34	7
	ArmanPrestige, да согласен. Тогда сразу в файле меняйте. 0

@ArmanPrestige Pied Piper 236 / 227 / 57 Регистрация: 15.01.2013 Сообщений: 855
	29.12.2016, 19:37 [ТС]	8
	Mikhail1990, что сразу менять? Хотелось бы конкретики, мне нужен более точный алгоритм 0

@Mikhail1990 27 / 26 / 6 Регистрация: 22.03.2014 Сообщений: 277
	29.12.2016, 19:48	9
	ArmanPrestige, можно кусками открывать файл по 1,5 гб отсортировать и удалить повторы, запомнить где было последнее считывание и приапендить новый кусок без повторов. ВОТ Внешняя сортировка 1

@ArmanPrestige Pied Piper 236 / 227 / 57 Регистрация: 15.01.2013 Сообщений: 855
	30.12.2016, 00:22 [ТС]	13
	Сообщение от kamre 2^32 бит = 2^32/8 байт = 2^32/2^3 = 2^(32 - 3) = 2^29 Я верно понимаю, что вы имеете в виду использование битовых полей? 0

@ArmanPrestige Pied Piper 236 / 227 / 57 Регистрация: 15.01.2013 Сообщений: 855
	30.12.2016, 12:37 [ТС]	15
	kamre, зачем вектор? лучше уже std::bitset 0

	02.01.2017, 18:50

@trdm 182 / 37 / 5 Регистрация: 29.01.2013 Сообщений: 253
	30.12.2016, 16:53	16
	Можно еще попробовать хранить структуры с диапазонами в виде мин/макс. Надо подумать 0

@alexu_007 661 / 662 / 106 Регистрация: 29.05.2015 Сообщений: 3,967
	01.01.2017, 16:53	17
	По моему - решение очевидное. Памяти нужно будет 2^32 бит. Читаешь из исходного файла 1-е число, устанавливаешь соотв. числу бит (номер которого в списке равен номеру числа) в true, скидываешь число в файл-приёмник, читаешь следующее, проверяешь бит, если true - число уже было, пропускаешь, если false - число раньше не встречалось, бит в true и число в файл-приёмник. И так далее до конца файла. Т.к. чисел разных 4-х битных всего 2^32, то и длина файла приёмника не может быть больше этого значения: каждой цифры по 1 штуке. Собсна, когда все цифры будут в файле приёмнике - дальше продолжать не имеет смысла. 0