Здравствуйте, Tonal-, Вы писали:
T>>... как лучше работать с большими объёмами строк? T>Но этот вопрос таки остаётся. T>Нужен поиск и замена подстроки.
Здравствуйте, D. Mon, Вы писали:
DM>Ограничение по памяти — 256 МБ.
это больше похоже не на практикум по *fp*, а на практикум по конкретным реализациям. интересоваться тем, как это делается в фп языках я бы рекомендовал только после того, как усвоен сам стиль фп программирования
Здравствуйте, MasterZiv, Вы писали:
>> ага. ты в курсе, что кол-во открытых файлов несколько ограничено?
MZ>Ага, а ты в курсе, что большинство предложенных решений построено MZ>по тому же принципу ? Я-то вот кэш открытых файлов сделал. MZ>Получилось много кода.
вообще-то я с самого начала подразумевал, что таких решений быть не должно. в фп языках не так уж сложно подготовить сначала данные в памяти чтобы затем писать по одному файлу
Здравствуйте, BulatZiganshin, Вы писали:
BZ>это больше похоже не на практикум по *fp*, а на практикум по конкретным реализациям.
Там фишка именно в дизайне — как обобщить сортировку на разные типы файлов с их нюансами. Я такую задачу решал на окамле с помощью модулей, но возможно есть более красивое решение.
BZ>интересоваться тем, как это делается в фп языках я бы рекомендовал только после того, как усвоен сам стиль фп программирования
Тогда прошу продемонстрировать этот самый стиль. Хотя бы костяк решения.
Здравствуйте, D. Mon, Вы писали:
DM>Там фишка именно в дизайне — как обобщить сортировку на разные типы файлов с их нюансами. Я такую задачу решал на окамле с помощью модулей, но возможно есть более красивое решение.
я может чего-то не понимаю, но о каком обобщении здесь идёт речь?
DM>Тогда прошу продемонстрировать этот самый стиль. Хотя бы костяк решения.
я как раз и говорю о том, что решение данной задачи не поможет развить фп-стиль программирования.
Здравствуйте, BulatZiganshin, Вы писали: T>>Для трёх буквочек можно нарисовать примерно так: BZ>ага. ты в курсе, что кол-во открытых файлов несколько ограничено?
Типа так:
#include <iostream>
#include <fstream>
#include <iterator>
#include <map>
#include <vector>
using namespace std;
typedef istream_iterator<string> word_iter_t;
typedef map<string, vector<string> > wmap_t;
typedef wmap_t::const_iterator wmap_iter_t;
typedef vector<string>::const_iterator witer_iter_t;
int main() {
wmap_t ofs;
ifstream words("words.txt");
for (word_iter_t cur(words), end; cur != end; ++cur) {
string fname = cur->substr(0, 3);
if (fname.size() > 0)
ofs[fname].push_back(*cur);
}
for (wmap_iter_t cur = ofs.begin(), end = ofs.end(); cur != end; ++cur) {
ofstream out(cur->first.c_str());
for (
witer_iter_t wcur = cur->second.begin(), end = cur->second.end();
wcur != end; ++wcur
)
out << *wcur << ' ';
}
}
Здравствуйте, D. Mon, Вы писали:
DM>1. Есть большой текстовый файл A (несколько гигов, заведомо не помещается в память), нужно сделать текстовый файл A1, содержащий все строки из А, но отсортированные в алфавитном порядке. Ограничение по памяти — 256 МБ.
import System.IO
import System.Directory
import Data.List
import Data.Maybe-- Разбиваем файл на куски определенного размера (заданного количеством строк)
-- Куски сортируем в памяти и записываем во временные файлы
-- Объединяем временные файлы в один отсортированный файл
sortBigFile srcFile dstFile maxSize = do
tempFiles <- splitFile maxSize srcFile
mergeChains tempFiles dstFile
mapM_ removeFile tempFiles -- удаляем мусор, который насоздавали
-- Возвращает ленивый список строк, содержащихся в файле
-- Позволяет работать со строками файла как со списком
-- В то же время не загружает полностью файл в памятьtype Stream = [String]
stream :: Handle -> IO Stream
stream handle = do
contents <- hGetContents handle
return $ lines contents
-- Делит файл на отсортированные куски размеров не больше maxSize строк
-- Функция возращает список временных файлов, содержащих отсортированные куски
splitFile :: Int -> FilePath -> IO [FilePath]
splitFile maxSize srcFile = do
h <- openFile srcFile ReadMode
s <- stream h
tempFiles <- splitFile' maxSize 0 s
hClose h
return tempFiles
-- Каждый кусок сортируется и записывается во временный файл
-- Имена временных файлов: temp0, temp1, и т.д.
-- xs - оставшиеся строки исходного файла, suffix - суффикс временного файла
splitFile' _ _ [] = return []
splitFile' maxSize suffix xs = do
let tempFile = "temp" ++ show suffix
let (chainLines, restLines) = splitAt maxSize xs
writeFile tempFile (unlines $ sort chainLines) -- сортировка и запись одного куска
restFiles <- splitFile' maxSize (suffix+1) restLines
return (tempFile : restFiles)
-- Объединяет отсортированные куски (fileNames) в один большой отсортированный файл dstFile
mergeChains :: [FilePath] -> FilePath -> IO ()
mergeChains fileNames dstFile = do-- dst <- dst' dstFile
dst <- openFile dstFile WriteMode
files <- mapM ((flip $ openFile) ReadMode) fileNames
strms <- mapM stream files
mergeChains' strms dst
mapM_ hClose files
hClose dst
-- Каждый объединяемый файл представлен потоком (ленивым списком) строк
-- Сравниваем первые строки потоков и минимальную строку отправляем в итоговый файл
-- streams - потоки строк временных файлов
-- dstHandle - итоговый файл
mergeChains' :: [Stream] -> Handle -> IO ()
mergeChains' streams dstHandle
| null strms = return ()
| otherwise = do hPutStrLn dstHandle minLine
mergeChains' (updateStreams strms) dstHandle
where
strms = filter (not.null) streams -- выкидываем обработанные потоки
minLine = minimum $ map head strms -- выбираем из всех потоков минимальную строку
-- В потоке, который содержал минимальную строку, переходим к следующим строкам
-- А остальные потоки оставляем без изменений
updateStreams (s:ss) | head s == minLine = (tail s) : ss
| otherwise = s : updateStreams ss
--------------
--- MAIN -----
-- main = sortBigFile "A" "A1" 10000
Не буду судить о пригодности этой задачи к практикуму ФП. Скажу лишь, что мне она добавила некоторых знаний.
Да и решить было просто интересно. Ну и ФП все же присутствует — вон тот же mergerChain' более-менее ФП-шный, плюс ленивость, работа с файлом как со списком и т.п.
Для тестов был создан файлик A и B, внутри которых — текст данной программы повторенный хз сколько раз.
Файл А — 11,5 Мб, 0,3 млн строк
Файл B — 91,5 Мб, 2,4 млн строк
В итоге:
обработка А — 30 временных файлов — 12 сек
обработка B — 240 временных файлов — 389 сек
Расход памяти для maxSize = 10000 строк по данным -sstderr около 15 Мб
splitFile — около 30% времени, mergerChains около 70%
В целом, около 50% времени занимает сравнение строк между собой.
Для сравнения попробовал запустить упрощенный вариант
main = do
content <- readFile "A"
writeFile "A1" (unlines $ sort $ lines content)
Для файла A — 7 сек, 313 Мб памяти
Для файла B — не получился результат
Сначала сказал, хочу больше виртуальной памяти. Добавил (оказалось была отключена, я даже и не знал работал целый год
Потом просто out of memory. Я так понял из-за ограничений на количество памяти для программ в Windows
Здравствуйте, Beam, Вы писали:
B>Не буду судить о пригодности этой задачи к практикуму ФП. Скажу лишь, что мне она добавила некоторых знаний.
если ограничивать число строк, а не объём занимаемой памяти — то нормально
main = do-- (Лениво) создаём отсортированные подсписки
sublists <- fmap sort1 getContents
-- Записываем их в файлы с именами 1..n
for (zip (map show [1..]) pairs) (uncurry writeFile)
-- Читаем (опять же лениво) содержимое всех ранее созданных файлов
sublists <- mapM (fmap lines readFile.show) [1..length sublists]
-- Сливаем их и записываем результат
putStr (unlines (mergesort' compare sublists)
sort1 = lines >>> unfoldr (\xs -> guard (xs>[]) >> splitAt 5000 xs) >>> map (sort>>>unlines)
-- Процедуру слияния упорядоченных списков можно найти в исходниках Data.List:
mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
mergesort' cmp [] = []
mergesort' cmp [xs] = xs
mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
merge_pairs cmp [] = []
merge_pairs cmp [xs] = [xs]
merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
merge cmp xs [] = xs
merge cmp [] ys = ys
merge cmp (x:xs) (y:ys)
= case x `cmp` y of
GT -> y : merge cmp (x:xs) ys
_ -> x : merge cmp xs (y:ys)
на самом деле, даже если я ни в чём не ошибся — этот код будет держать все данные в памяти до победного. extra points — за изящное решение этой маааленькой проблемы
Здравствуйте, BulatZiganshin, Вы писали:
BZ>если ограничивать число строк, а не объём занимаемой памяти — то нормально BZ>
BZ>main = do-- (Лениво) создаём отсортированные подсписки
BZ> sublists <- fmap sort1 getContents
BZ> -- Записываем их в файлы с именами 1..n
BZ> for (zip (map show [1..]) pairs) (uncurry writeFile)
BZ> -- Читаем (опять же лениво) содержимое всех ранее созданных файлов
BZ> sublists <- mapM (fmap lines readFile.show) [1..length sublists]
BZ> -- Сливаем их и записываем результат
BZ> putStr (unlines (mergesort' compare sublists)
BZ>sort1 = lines >>> unfoldr (\xs -> guard (xs>[]) >> splitAt 5000 xs) >>> map (sort>>>unlines)
BZ>
1. Так и не смог я это запустить. В принципе идея ясна, но хочется увидеть решение, которе хотя бы компилируется (в т.ч. импорт)
А в идеале — полный пример, с открытием, закрытием файлов и пр.
2. Я думаю ленивость здесь теряется на readFile, т.к. файл закрывается и все данные попадают в память.
Здравствуйте, Beam, Вы писали:
B>1. Так и не смог я это запустить. В принципе идея ясна, но хочется увидеть решение, которе хотя бы компилируется (в т.ч. импорт)
ну симпортируйте стандартные Data.List, Control.Monad и прочая
B>А в идеале — полный пример, с открытием, закрытием файлов и пр.
это полный пример
B>2. Я думаю ленивость здесь теряется на readFile, т.к. файл закрывается и все данные попадают в память.
нет. readFile = openFile >>= hGetContents, т.е. он читает файл так же лениво и безалаберно
Здравствуйте, BulatZiganshin, Вы писали:
BZ>я может чего-то не понимаю, но о каком обобщении здесь идёт речь?
Обобщение алгоритма сортировки на две подзадачи: в одном случае просто сортировка, в другом — с оставлением только уникальных строк и подсчетом их количества. Например, там могут быть разные функции чтения, записи, сравнения и комбинирования, а функция сортировки — одна общая.
BZ>я как раз и говорю о том, что решение данной задачи не поможет развить фп-стиль программирования.
Тут немного ранее обсуждали, что на слишком маленьких задачах не продемонстрировать ФП-подход к дизайну, чтобы можно было его сравнить с ООП-дизайном. Мне показалось, что данная задача уже дает такую возможность.
Здравствуйте, D. Mon, Вы писали:
BZ>>я может чего-то не понимаю, но о каком обобщении здесь идёт речь?
DM>Обобщение алгоритма сортировки на две подзадачи: в одном случае просто сортировка, в другом — с оставлением только уникальных строк и подсчетом их количества. Например, там могут быть разные функции чтения, записи, сравнения и комбинирования, а функция сортировки — одна общая.
можно конечно, но по-моему это слишком сложно. проще поставить агрегатор после merge
BZ>>я как раз и говорю о том, что решение данной задачи не поможет развить фп-стиль программирования.
DM>Тут немного ранее обсуждали, что на слишком маленьких задачах не продемонстрировать ФП-подход к дизайну, чтобы можно было его сравнить с ООП-дизайном. Мне показалось, что данная задача уже дает такую возможность.
проблема на самом деле в том, что фп дизайн по опыту программирования в яве понять так же невозможно, как ооп дизайн по опыту ассемблера
кроме того, обсуждать его надо не на примере полного решения маленьких задач, а на разборе именно дизайна крупных задач или библиотек
Здравствуйте, D. Mon, Вы писали:
DM>Здравствуйте, BulatZiganshin, Вы писали:
BZ>>я может чего-то не понимаю, но о каком обобщении здесь идёт речь?
DM>Обобщение алгоритма сортировки на две подзадачи: в одном случае просто сортировка, в другом — с оставлением только уникальных строк и подсчетом их количества. Например, там могут быть разные функции чтения, записи, сравнения и комбинирования, а функция сортировки — одна общая.
Неплохо, только на файле из 20 млн строк получится нужно одновременно открыть 2000 файлов. ОС позволит? Попарный мердж, как у Булата, тут подойдет лучше.
А теперь самое интересное — пункт 2 (про подсчет уникальных строк). Интересно, как сильно надо будет менять программу для его реализации.
Здравствуйте, D. Mon, Вы писали:
B>>mergeChains :: [FilePath] -> FilePath -> IO () DM>Неплохо, только на файле из 20 млн строк получится нужно одновременно открыть 2000 файлов. ОС позволит? Попарный мердж, как у Булата, тут подойдет лучше.
Ну, все не так плохо. Там же задается maxSize.
Вот расход памяти для разных maxSize, применительно к тестовым файлам.
maxSize = 20000 — 29 Mb
maxSize = 50000 — 61 Mb
maxSize = 200000 — 273 Mb
т.е. используя maxSize = 200 тыс., файл 20 млн. строк даст 10 файлов
Хотя, конечно, когда-нибудь упремся в количество файлов
Попарное слияние увеличивает время работы алгоритма.
Если мы держим только несколько файлов открытыми (не все), то и слияние в данный момент можем сделать только на них. Мы их читаем, потом объединяем в один файл побольше. Но этот файл (который побольше) снова надо объединять с другими, а значит мы его снова должны прочитать. В любом случае, если делать серьезную реализацию, надо учитывать возможность ограничения на количество открытых файлов, а соответственно — делать промежуточное слияние.
Алгоритм Булата практически ничем не отличается. Только он красивее выглядит Алгоритм слияния хоть и "выглядит попарным" (так проще), на самом деле для его работы также открываются все файлы одновременно.
К тому же, на текущий момент, там все данные загружаются в память, а значит вообще временные файлы не нужны.
Надежда была на полную ленивость, но программа получается энергичная. Хотелось бы это исправить.
DM>А теперь самое интересное — пункт 2 (про подсчет уникальных строк). Интересно, как сильно надо будет менять программу для его реализации.
Позже попробую написать. Но принцип, думаю, будет такой:
В mergeChains', там где строка выводится в итоговый файл добавим функцию, которая будет подсчитывать количество повторов последней строки, а затем выводить ее саму и количество в другой файл A2.
Алгоритм слияния хоть и "выглядит попарным" (так проще), на самом деле для его работы также открываются все файлы одновременно.