ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / замена 2 произвольных строк в огромном файле
25 сообщений из 118, страница 1 из 5
  1  все
замена 2 произвольных строк в огромном файле
    #39052604
polin11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
polin11
Гость
Есть задача, поменять в огромном текстовом файле (несколько Гб) 2 произвольные строки.
Написал 2 программы: в основе 1 берем vector<string> записываем все строки,
затем меняем методом swap 2 строки, удаляем данные файла, записываем в файл
vector.
Основа 2 программы - читаем 2 строки, записываем данные в новый файл
в правильном порядке, удаляем исходный файл, переименовываем новый файл.
Проблема в том, что программа работает 5 мин, на файле 100 Мб, на файле 1ГБ, более часа.
Кто знает другой способ поменять 2 произвольные строки в огромном файле.
...
Рейтинг: 0 / 0
16.09.2015, 11:52
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39052618
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
polin11, исходники можно посмотреть?
...
Рейтинг: 0 / 0
16.09.2015, 12:08
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39052692
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Если задача просто поменять две строки файла местами, т.е. размер файла не меняется, то файл целиком вообще читать не надо:
1. Читаешь файл пока не найдешь где эти строки.
2. Читаешь в буфер первую строку, промежуток между строками, вторую строку
3. Встаешь в начало первой, пишешь вторую, промежуток, первую.
...
Рейтинг: 0 / 0
16.09.2015, 13:16
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39052795
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
polin11,

Задача не сложная. Вы просто где-то очень сильно напортачили. Я для эксперимента только что сжал WinRar-ом видео файл на 5 (пять) гигабайт за 3 (три) минуты с компрессией Best. А это задача на N порядков сложнее (в плане вычислений) вашей.
...
Рейтинг: 0 / 0
16.09.2015, 13:58
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39052860
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
polin11Кто знает другой способ поменять 2 произвольные строки в огромном файле.

sed
...
Рейтинг: 0 / 0
16.09.2015, 14:24
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053340
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petravpolin11,

Задача не сложная. Вы просто где-то очень сильно напортачили. Я для эксперимента только что сжал WinRar-ом видео файл на 5 (пять) гигабайт за 3 (три) минуты с компрессией Best. А это задача на N порядков сложнее (в плане вычислений) вашей.

Petrav

Это то о чём я говорил несколько топиков назад. Периодически (раз в квартал)
появляется новичёк которому надо либо отсортировать терабайт int-ов. Либо
В терабайтном файле перевернуть все строки revers()-ом наоборот.
Либо написать Архиватор Бабушкина. Либо базу данных на хеш-арреях
которая будет работать быстрее чем кеш первого уровня.

Кстати в данной задаче я-бы создать интерфейс ITextReadable с версионностью
который перевернёт вам 2 строки "виртуально". Вобщем думайте
а я спать.
...
Рейтинг: 0 / 0
16.09.2015, 23:42
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053368
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
maytonpetravpolin11,

Задача не сложная. Вы просто где-то очень сильно напортачили. Я для эксперимента только что сжал WinRar-ом видео файл на 5 (пять) гигабайт за 3 (три) минуты с компрессией Best. А это задача на N порядков сложнее (в плане вычислений) вашей.

Petrav

Это то о чём я говорил несколько топиков назад. Периодически (раз в квартал)
появляется новичёк которому надо либо отсортировать терабайт int-ов. Либо
В терабайтном файле перевернуть все строки revers()-ом наоборот.
Либо написать Архиватор Бабушкина. Либо базу данных на хеш-арреях
которая будет работать быстрее чем кеш первого уровня.
Хех. Так ведь на таких задачах молодёжь и учится понимать как на самом деле работает компьютер. И решение молодёжью таких задач нужно только приветствовать. Потому что именно они (решающие такие задачи) — будущие спецы. Понять такие базовые вещи — дальше уже нет границ. Хоть виртуальная машина, хоть тонкий клиент в браузере — всё понятно, даже сам мог бы поучаствовать в их разработке.

Другое дело какой-нибудь молодой специалист, который всегда оперировал только высокоуровневыми инструментами и даже представить себе не может как на самом деле они внутри реализованы. Так он этими инструментами и воспользоваться эффективно не сможет. Или не сможет поучаствовать в разработке новой технологии, какой-нибудь Russian C#+-. :)
...
Рейтинг: 0 / 0
17.09.2015, 00:29
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053399
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
polin11Есть задача, поменять в огромном текстовом файле (несколько Гб) 2 произвольные строки.
Написал 2 программы: в основе 1 берем vector<string> записываем все строки,
затем меняем методом swap 2 строки, удаляем данные файла, записываем в файл
vector.
Основа 2 программы - читаем 2 строки, записываем данные в новый файл
в правильном порядке, удаляем исходный файл, переименовываем новый файл.
Проблема в том, что программа работает 5 мин, на файле 100 Мб, на файле 1ГБ, более часа.
Кто знает другой способ поменять 2 произвольные строки в огромном файле.

Какая асимптотика у вашего первого алгоритма ? Не O(len(main_s)*max{len(subs1),len(subs2)}) ?
Второй ваш алгоритм я не понял.

Алгоритм такой:
1. Найти 1 строку
2. Найти 2 строку
3. Отправить на поток вывод в правильном порядке результат

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

Так вот, основная сложность в поиске каждой строки. Если использовать алгоритм посимвольного сравнения асимптотическая сложность будет O(len(main)len(subs)). Быстрым алгоритмом, и, кроме того, алгоритмов с лучшей асимптотикой быть просто не может, является алгоритм Кнута-Морриса-Пратта. Более подробно можно посмотреть в книге Алгоритмы: Построение и анализ (Корман, Лейзерсон, ...)
...
Рейтинг: 0 / 0
17.09.2015, 02:18
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053464
BagaBaga
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BagaBaga
Участник
polin11берем vector<string> записываем все строки,
Зачем Вам столько тянуть в память? А если будет 16 Гб? Или 32? Или 320?

polin11Основа 2 программы - читаем 2 строки, записываем данные в новый файл
в правильном порядке, удаляем исходный файл, переименовываем новый файл
Опять же, для чего второй файл? Чтобы затребовать двойное место для работы? Вам же подсказали, что общий размер файла не меняется. Если строки одинакового размера, то всё совсем просто (два позиционирования, два чтения, две записи). Если разные, то чуть-чуть сложнее: придётся ещё "подтягивать" данные между концом первой и второй строки.

К стати, так и непонятно, как задаётся, какие же строки нужно заменить.
...
Рейтинг: 0 / 0
17.09.2015, 07:52
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053487
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
SashaMercuryТак вот, основная сложность в поиске каждой строки. Если использовать алгоритм посимвольного сравнения асимптотическая сложность будет O(len(main)len(subs)). Быстрым алгоритмом, и, кроме того, алгоритмов с лучшей асимптотикой быть просто не может, является алгоритм Кнута-Морриса-Пратта. Более подробно можно посмотреть в книге Алгоритмы: Построение и анализ (Корман, Лейзерсон, ...)

преждевременная оптимизация, зуб даю - len(subs) много меньше len(main)
...
Рейтинг: 0 / 0
17.09.2015, 08:29
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053500
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryАлгоритм такой:
1. Найти 1 строку
2. Найти 2 строку
3. Отправить на поток вывод в правильном порядке результат

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

Так вот, основная сложность в поиске каждой строки. Если использовать алгоритм посимвольного сравнения асимптотическая сложность будет O(len(main)len(subs)). Быстрым алгоритмом, и, кроме того, алгоритмов с лучшей асимптотикой быть просто не может, является алгоритм Кнута-Морриса-Пратта. Более подробно можно посмотреть в книге Алгоритмы: Построение и анализ (Корман, Лейзерсон, ...)
Саш тут основная сложность не в поиске. В данной постановке практически пофиг каким алгоритмом
поиска ты будешь искать. Можно даже грубой силой. Это не влияет на чтение "нескольких гигабайт".
А вот последующая замена (рассматривая кейсы когда одна из строк - пустая или искомая строка
вдруг (!) внезапно встречается больше чем 1 раз) мы получаем довольно сложный грузящий подсистему
I/O процесс напоминающий по сути работу дефрагментатора. Вангую что существует такой расклад
входных данных при котором действительно легче создать новый файл с заменой чем тасовать блоки символов в обе стороны.
...
Рейтинг: 0 / 0
17.09.2015, 08:46
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053510
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
maytonлегче создать новый файл
это конечно за рамками задачи - но при аварийном завершении процесса не хотелось бы оставлять данные в неконсистентном состоянии
...
Рейтинг: 0 / 0
17.09.2015, 09:02
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053519
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я помню в универе в рамках курсового мы с приятелем выдумывали как
выкусывать из DOS/FAT16 файла кусок из середины кратный 512 байтам.
...
Рейтинг: 0 / 0
17.09.2015, 09:16
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053520
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Изопропилmaytonлегче создать новый файл
это конечно за рамками задачи - но при аварийном завершении процесса не хотелось бы оставлять данные в неконсистентном состоянии
ИМХУ с новым файлом этой проблемы как раз не будет, если писать новый, переименовывать, удалять старый.

С перезаписью можно журнал транзакций добавить. В принципе он есть на уровне ФС, но вопрос как ФС рассматривает перезапись большого куска файла, например несколько Мб, как одну транзакцию или несколько?

PS polin11 пропал. А ему тут столько насоветовали. Вернется - будет долго медитировать над тем как его тему развили
...
Рейтинг: 0 / 0
17.09.2015, 09:17
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053606
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
polin11Есть задача, поменять в огромном текстовом файле (несколько Гб) 2 произвольные строки.
Проблема в том, что программа работает 5 мин, на файле 100 Мб, на файле 1ГБ, более часа.
Кто знает другой способ поменять 2 произвольные строки в огромном файле.

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

В принципе можно (если менять нужно только 2 строки) найти их в файле, и записать с начала первой строки вторую, потом кусок между ними, потом первую.

Т.е. заменяем A на B

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
X
X
A
Y
Y
Y
B
X
X
X
X

сохраняем в памяти A, затем YYY, затем B, потом пишем:

1) сначала B
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
X
X
B
.
.
.
.
X
X
X
X

2) затем YYY
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
X
X
B
Y
Y
Y
.
X
X
X
X

2) затем A
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
X
X
B
Y
Y
Y
A
X
X
X
X


Но это надо в памяти кусок YYY держать, что может быть накладно.
Можно переписывать кусок YYY по частям, тогда нужно уметь хранить в памяти 2 таких части.
...
Рейтинг: 0 / 0
17.09.2015, 10:44
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053758
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
MasterZivНо это надо в памяти кусок YYY держать, что может быть накладно.
не надо - подвигать можно и не сохраняя в памяти ничего, одного буфера достаточно
...
Рейтинг: 0 / 0
17.09.2015, 12:29
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053764
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Проще в память замапить, а дальше пусть ОС решает в кэше подержать или сразу на диск.
...
Рейтинг: 0 / 0
17.09.2015, 12:31
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053826
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dima TПроще в память замапить, а дальше пусть ОС решает в кэше подержать или сразу на диск.
студент поработать должен.

а простота может испариться, если поставить ограничения - 32-разрядная сиcтема, и файл в 4GB
...
Рейтинг: 0 / 0
17.09.2015, 13:13
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053853
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ИзопропилDima TПроще в память замапить, а дальше пусть ОС решает в кэше подержать или сразу на диск.
студент поработать должен.

а простота может испариться, если поставить ограничения - 32-разрядная сиcтема, и файл в 4GB
Я категорически против решать подобные задачи любым mmap. Это уход
в сторону от алгоритмизации. И перенос проблем больной головы заказчика
на бедное железо.

Усилия в решении лежат в плоскости 80% понимания ТЗ и limitations.
А именно: какие строки? Какой длины strlen(a), strlen(b) ? Может-ли строка B быть пустой?
Может ли в файле быть много замен?

10% в плоскости предварительной подготовки (текстовик можно индексировать).
Еще 5% на модификацию исходных данных. Можно создать linked-list-on-filesystem.
и модифицировать его.

И еще процентов 5 усилий можно кинуть на убеждение того что заказчику это
не надо (получение на выходе ФАЙЛА). А надо создать интерфейс "версионного текстового файла" и форсировать COW
к примеру. Сам файл в руки не давать. А только интерфейс чтения строк.
...
Рейтинг: 0 / 0
17.09.2015, 13:33
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053885
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Изопропилстудент поработать должен.
с этим согласен
Изопропила простота может испариться, если поставить ограничения - 32-разрядная сиcтема, и файл в 4GB
Хоть 100 ГБ, для реализации этого алгоритма достаточно замапить только кусок в котором замена. Если кусок больше 2 Гб то на х32 будет проблема.
maytonЯ категорически против решать подобные задачи любым mmap. Это уход
в сторону от алгоритмизации. И перенос проблем больной головы заказчика
на бедное железо.

Усилия в решении лежат в плоскости 80% понимания ТЗ и limitations.
...
Я про конкретную задачу 18155678 и 18159433
Ее эффективнее всего решать с мап. Потому что при размещении промежуточных данных в памяти может возникнуть своп в файл подкачки если памяти не хватит, и ты из своего кода этим управлять никак не сможешь. В случае с мап этим управляет ОС, изменяемый файл является файлом подкачки для данного куска памяти, все записанное, что не влазит в память, ОС просто скинет на диск сразу в этот файл, без лишних дисковых операций. И алгоритмизацию тут никто не отменял.
...
Рейтинг: 0 / 0
17.09.2015, 13:56
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053906
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dima TЕе эффективнее всего решать с мап.
ага, mmap вместо последовательного доступа - охрененно эффективно.
...
Рейтинг: 0 / 0
17.09.2015, 14:09
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053935
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ИзопропилDima TЕе эффективнее всего решать с мап.
ага, mmap вместо последовательного доступа - охрененно эффективно.

Я про виндовый мап писал. CreateFileMapping(). В виндовсе эффективно. Возможно в линуксах по-другому устроено, не пользовался.
...
Рейтинг: 0 / 0
17.09.2015, 14:24
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053942
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TИзопропилпропущено...

ага, mmap вместо последовательного доступа - охрененно эффективно.

Я про виндовый мап писал. CreateFileMapping(). В виндовсе эффективно. Возможно в линуксах по-другому устроено, не пользовался.
Весьма спорно. У нас нет сравнительных бенчмарков эффективности реализации mmap в Windows/Linux.
Или требуется контр-пруф.
...
Рейтинг: 0 / 0
17.09.2015, 14:32
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053969
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petrav
Участник
Может легче кластеры на файловой системе переставить? Насколько я понимаю файл — это список кластеров на носителе данных. Вот этот список и нужно подредактировать не перемещая сами данные.
...
Рейтинг: 0 / 0
17.09.2015, 14:46
| Ответить | Цитировать | Написать  
замена 2 произвольных строк в огромном файле
    #39053973
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima Tпропущено...

Я про виндовый мап писал. CreateFileMapping(). В виндовсе эффективно. Возможно в линуксах по-другому устроено, не пользовался.
Весьма спорно. У нас нет сравнительных бенчмарков эффективности реализации mmap в Windows/Linux.
Или требуется контр-пруф.
Про линукс просто не знаю, не изучал, не пользовался. Наверно что-то похожее.
По виндовсу уже писал и пример приводил когда "ошибки страниц" обсуждали.
Упрощенно: виндовс каждой странице памяти назначает файл подкачки, это либо реальный файл, либо своп (pagefile.sys).
1. Если ты замапил файл 1Гб в памяти, то этот момент ни одного байта из файла не прочиталось. Просто менеджер памяти сопоставил кусок адресного пространства с файлом.
2. Если ты обратился к середине куска, то прочитается сопоставленный кусок файла выравненный до размера страницы памяти (4 Кб)

Но если ты выделил память (ей сопоставился своп) прочитал из файла кусок в эту память, и кусок не влез, то он сначала частично уйдет в своп, затем когда ты пишешь в файл идет сначала чтение из свопа в память (чего нет в памяти). Ну и зачем тут своп если вместо него сразу можно использовать исходный файл?
...
Рейтинг: 0 / 0
17.09.2015, 14:48
| Ответить | Цитировать | Написать  
25 сообщений из 118, страница 1 из 5
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / замена 2 произвольных строк в огромном файле
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]