почитать файл за один проход. как?
ниасилил
Расскажи, что ты хочешь получить, а не что ты делаешь.
Пока ничего не понятно.
Расскажи, что ты хочешь получить, а не что ты делаешь.
Пока ничего не понятно.
за 1 проход выясняем какие ячейки вообще есть и сколько под каждую нужно памяти, далее аллоцируем, далее второе чтение файла, записываем всю инфу, превращая ссылки на имена в ссылки на int (все структуры кладутся в массив, значит есть индекс,Как структуры "кладутся в массив" если мы их "аллоцируем". Это какие-то другие структуры, или речь идет о массиве указателей ? Что такое "ссылки на int" ?
Если и правда массив указателей, и индекс в качестве ссылки, то вроде ничего не мешает заполнять данные на первом проходе. Может причина в загадочной "доп инфа типа смещение по х и у-это move {900 800}" ?
опишу упрощенно на си ++ =)
geo_tree = new cell[1000000] ;//константа зашита, иначе 3 раза пробегать по файлу;
class cell {
char*name;
//три массива одной и той же длины.
int *movex;
int *movey;
int *referencies;
}
в переменную geo_tree надо прочитать весь файл.
каждый новый cellx кладется в этот массив (соответственно у него появляется некоторый
индекс Index, который будет использоваться в другой ячечке при появлении i-го call cellx move {5 6}
в массив
referencies[i]=Index;
movex[i]=5;
movey[i]=6;
i++;// переходим к следующей записи
Все же нужно уметь сформулировать задачу.
Если я правильно понял, то конечно, никакие два прохода не нужны. Можно все сделать за один.
Могу предложить перейти от массива к дереву ( почитать литературу про списки/деревья можно в Вирте) . Дерево можно реализовать самому или взять готовую реализацию. Можно сразу попробовать использовать STL.
Как "дикий" вариант могу предложить хранить все данные в XML и пользоваться существующими парсерами XML.
Если я правильно понял, то конечно, никакие два прохода не нужны. Можно все сделать за один.
Могу предложить перейти от массива к дереву ( почитать литературу про списки/деревья можно в Вирте) . Дерево можно реализовать самому или взять готовую реализацию. Можно сразу попробовать использовать STL.
Как "дикий" вариант могу предложить хранить все данные в XML и пользоваться существующими парсерами XML.
Можно ли использовать x из cellx в качестве индекса ?
Если нет, то как ты определяешь индекс ячейки, на которую ссылается данная (для заполнения referencies[i] ) ? Неужели пробегаешь весь массив ?
И вообще, используй stl. std::vector<cell> geo_tree и так далее.
Если нет, то как ты определяешь индекс ячейки, на которую ссылается данная (для заполнения referencies[i] ) ? Неужели пробегаешь весь массив ?
И вообще, используй stl. std::vector<cell> geo_tree и так далее.
данные хранятся именно в том формате, что я описал на си
то есть именно массив ячеек и каждая ячейка устроена именно так.
файл с данными тоже имеет конкретный формат, который я описал..так что никаких хмл тут не стоит приляпывать.
поэтому за первый прогон выясняются все имена ячеек и сколько call содержится внутри каждой (получаем инфу как аллоцировать каждую ячейку за второй прогон запоняем уже аллоцированные ячейки.
ячейки слишком большие, чтобы я делал свои деревья для единственного прогона по файлу, а потом копировал считанное в фиксированный формат, описанный выше.
поиск индекса по имени-бинарный поиск в списке имен структур (список хранится отдельно).
вопрос- как при таких ограничениях сделать 1 чтение файла?
можно конечно делать reallocate, если место внутри ячейки кончилось, но непонятно на сколько увеличивать? или удваивать? в итоге размер должен в точности равняться кол-ву call. много реаллокейтов замедлит прогу.
пс: раньше делался тройной проход: имена ячеек считывались, потом размер каждой ячейки, затем содержимое ячеек.
я объединил первые два в один проход. вот и родился вопрос-сжать все до 1 прохода. чтение по NFS идет, поэтому это критично для больших файлов.
то есть именно массив ячеек и каждая ячейка устроена именно так.
файл с данными тоже имеет конкретный формат, который я описал..так что никаких хмл тут не стоит приляпывать.
поэтому за первый прогон выясняются все имена ячеек и сколько call содержится внутри каждой (получаем инфу как аллоцировать каждую ячейку за второй прогон запоняем уже аллоцированные ячейки.
ячейки слишком большие, чтобы я делал свои деревья для единственного прогона по файлу, а потом копировал считанное в фиксированный формат, описанный выше.
поиск индекса по имени-бинарный поиск в списке имен структур (список хранится отдельно).
вопрос- как при таких ограничениях сделать 1 чтение файла?
можно конечно делать reallocate, если место внутри ячейки кончилось, но непонятно на сколько увеличивать? или удваивать? в итоге размер должен в точности равняться кол-ву call. много реаллокейтов замедлит прогу.
пс: раньше делался тройной проход: имена ячеек считывались, потом размер каждой ячейки, затем содержимое ячеек.
я объединил первые два в один проход. вот и родился вопрос-сжать все до 1 прохода. чтение по NFS идет, поэтому это критично для больших файлов.
Количество call известно к окончанию описания ячейки, так ? Значит, их количество - не проблема, можно например считать всю ячейку в память текстом, посчитать строки, выделить память, заполнить.
Загоняешь все строки в map<string, pair<int,int>> при первом появлении. Первый int - id строки, второй - индекс соответствующей ячейки в массиве. В ссылках, вместо индекса, кладешь id строки. При загрузке ячейки записываешь ее индекс в этот map. Потом, вторым проходом _по памяти_ заменяешь id строк на индексы.
Загоняешь все строки в map<string, pair<int,int>> при первом появлении. Первый int - id строки, второй - индекс соответствующей ячейки в массиве. В ссылках, вместо индекса, кладешь id строки. При загрузке ячейки записываешь ее индекс в этот map. Потом, вторым проходом _по памяти_ заменяешь id строк на индексы.
Количество call известно к окончанию описания ячейки, так ? Значит, их количество - не проблема, можно например считать всю ячейку в память текстом, посчитать строки, выделить память, заполнить.
--- в этом и есть основная задача
нет возможности хранить ячейку в 2 экземплярах
пример: есть всего две ячейки
нет у меня возможности хранить cell1 в 2 экземплярах, но могу в одном.
--------------
Загоняешь все строки в map<string, pair<int,int>> при первом появлении. Первый int - id строки, второй - индекс соответствующей ячейки в массиве. В ссылках, вместо индекса, кладешь id строки. При загрузке ячейки записываешь ее индекс в этот map. Потом, вторым проходом _по памяти_ заменяешь id строк на индексы.
--- это решаешь совсем другую задачу: как call превратить в правильный reference.
--- в этом и есть основная задача
нет возможности хранить ячейку в 2 экземплярах
пример: есть всего две ячейки
cell1 {
call cell2 move {0 1}
call cell2 move {0 2}
call cell2 move {0 3}
.....
call cell2 move {0 800999999}
}
cell2 {
rectangle 10 x 20
}
нет у меня возможности хранить cell1 в 2 экземплярах, но могу в одном.
--------------
Загоняешь все строки в map<string, pair<int,int>> при первом появлении. Первый int - id строки, второй - индекс соответствующей ячейки в массиве. В ссылках, вместо индекса, кладешь id строки. При загрузке ячейки записываешь ее индекс в этот map. Потом, вторым проходом _по памяти_ заменяешь id строк на индексы.
--- это решаешь совсем другую задачу: как call превратить в правильный reference.
Это здорово. Мы наконец выяснили, в чем состоит задача 
Вариант с realloc всем устраивает, кроме возможного замедления программы ?
Напиши свой memory management. Выделяешь в начале очень большой кусок памяти, забиваешь в него подряд данные первой ячейки, потом второй, третьей, т.д. А в ячейках только указатели расставляешь. Если переполнится - realloc. А лучше сразу выделить просто охренительный кусок памяти.
Вариант с realloc всем устраивает, кроме возможного замедления программы ?
Напиши свой memory management. Выделяешь в начале очень большой кусок памяти, забиваешь в него подряд данные первой ячейки, потом второй, третьей, т.д. А в ячейках только указатели расставляешь. Если переполнится - realloc. А лучше сразу выделить просто охренительный кусок памяти.
Это здорово. Мы наконец выяснили, в чем состоит задачаэто гуд
)не только. появляется опять же дублирование ячейки
Вариант с realloc всем устраивает, кроме возможного замедления программы ?
1) уже имеем длинный массив, но нет места
2) делаем allocate длиннее на 200 единиц
3) копируем инфу
4) delete [] прежний кусок.
на этапе 2) появляется удвоение памяти
много этапов 3) вызовет экспоненциальное замедление проги ;(
непонятно что такое "охренительный" . прога запускается на разных тачках..там эти понятия различны..в общем не пойдет.
Напиши свой memory management. Выделяешь в начале очень большой кусок памяти, забиваешь в него подряд данные первой ячейки, потом второй, третьей, т.д. А в ячейках только указатели расставляешь. Если переполнится - realloc. А лучше сразу выделить просто охренительный кусок памяти
А разве нет константы типа 1000000 в
"geo_tree = new cell[1000000] " для длины ячейки?
"geo_tree = new cell[1000000] " для длины ячейки?
это кол-во различных ячеек-зашито в проге.
содержимое каждой ячейки не ограничивается этой константой.
содержимое каждой ячейки не ограничивается этой константой.
Неужели никак не оценить общий размер данных ?
Тогда malloc больших кусков. Короче, что-то вроде stl rope.
Через размер файла можно оценить объем структуры хранения.
Linux позволяет выделять памяти сколько угодно, пока ты ее не используешь. Optimistic memory allocation strategy. Если твоя система действует также, то можешь просто выделить памяти с запасом.
Тогда malloc больших кусков. Короче, что-то вроде stl rope.
Через размер файла можно оценить объем структуры хранения.
Linux позволяет выделять памяти сколько угодно, пока ты ее не используешь. Optimistic memory allocation strategy. Если твоя система действует также, то можешь просто выделить памяти с запасом.
1) уже имеем длинный массив, но нет места
2) делаем allocate длиннее на 200 единиц
3) копируем инфу
4) delete [] прежний кусок.
на этапе 2) появляется удвоение памяти
много этапов 3) вызовет экспоненциальное замедление проги ;(
-------
Чувак, ты не прав. Если не тупить (аллокать всегда в два раза больше (не += 200, а *= 2 но только тогда, когда нужно то:
1) Прога сожрёт не более чем в два раза больше памяти, чем необходимо. (Ладно, в три, если реаллок глюканёт)
2) Накладные расходы на копирование будут жрать O(n * С) времени, где С = 1 / (1 - 1/multiplier где multiplier - это то, на сколько ты увеличиваешь массив, то есть например 2. Это такая полная хуйня, что даже стыдно о ней упоминать.
Если пункт 1) тебя не устраивает, то можешь умножать не на 2, а на 1.2, например. Тогда у тебя вырастет константа (с 2 до 6 что не страшно.
Короче, не иппи моск, делай как все - реаллоком. Можешь, конечно, написать свой мендеджер памяти, который должен общаться напрямую с виндой, дабы просить у неё память в терминах виртуальных страниц (афаик они при этом физически могут оказываться фрагментированными, но на перформанс оно не влияет, и копировать не нужно, так что их можно просить по одной за раз). Но я бы не стал.
И это, не используй new/delete, используй malloc/realloc/free.
Да, ещё, если ты не будешь аллокать память ещё подо что нибудь (или поступишь хитро: аллокнешь много памяти, потом ещё столько же под первый кусок массива, освободишь первый кусок памяти, чтобы все дальнейшие побочные аллоки брали память из пустого места от первого куска то реаллок не будет ничего копировать, так как за концом реаллокуемого куска будет свободная память.
упд: поправил оценку сложности. Чота меня проглючило...
2) делаем allocate длиннее на 200 единиц
3) копируем инфу
4) delete [] прежний кусок.
на этапе 2) появляется удвоение памяти
много этапов 3) вызовет экспоненциальное замедление проги ;(
-------
Чувак, ты не прав. Если не тупить (аллокать всегда в два раза больше (не += 200, а *= 2 но только тогда, когда нужно то:
1) Прога сожрёт не более чем в два раза больше памяти, чем необходимо. (Ладно, в три, если реаллок глюканёт)
2) Накладные расходы на копирование будут жрать O(n * С) времени, где С = 1 / (1 - 1/multiplier где multiplier - это то, на сколько ты увеличиваешь массив, то есть например 2. Это такая полная хуйня, что даже стыдно о ней упоминать.
Если пункт 1) тебя не устраивает, то можешь умножать не на 2, а на 1.2, например. Тогда у тебя вырастет константа (с 2 до 6 что не страшно.
Короче, не иппи моск, делай как все - реаллоком. Можешь, конечно, написать свой мендеджер памяти, который должен общаться напрямую с виндой, дабы просить у неё память в терминах виртуальных страниц (афаик они при этом физически могут оказываться фрагментированными, но на перформанс оно не влияет, и копировать не нужно, так что их можно просить по одной за раз). Но я бы не стал.
И это, не используй new/delete, используй malloc/realloc/free.
Да, ещё, если ты не будешь аллокать память ещё подо что нибудь (или поступишь хитро: аллокнешь много памяти, потом ещё столько же под первый кусок массива, освободишь первый кусок памяти, чтобы все дальнейшие побочные аллоки брали память из пустого места от первого куска то реаллок не будет ничего копировать, так как за концом реаллокуемого куска будет свободная память.
упд: поправил оценку сложности. Чота меня проглючило...
Речь идет о заполнении массивов с move_x, move_y для каждой ячейки. А их может быть много, и они могут быть маленькими. Если не повезет (не угадаем с начальным размером то будет либо большой перерасход памяти, либо по реаллоку на каждый такой массив, то есть по 2 на ячейку.
Если же все эти данные лепить в один большой массив (как я раньше предлагал то эта проблема решается, появляется другая: если где-то вызовется какой-то malloc, то realloc большого массива приведет к его копированию. Это неприемлемо. Значит, надо _все_ данные хранить в большом массиве - получаем свой менеджер памяти.
Если же все эти данные лепить в один большой массив (как я раньше предлагал то эта проблема решается, появляется другая: если где-то вызовется какой-то malloc, то realloc большого массива приведет к его копированию. Это неприемлемо. Значит, надо _все_ данные хранить в большом массиве - получаем свой менеджер памяти.
я бы не стал называть десять строчек кода "менеджером памяти" =)
Оставить комментарий
Maurog
имеется большой файл в котором хранится дерево следующим образом:то есть имеются ячейки + вызовы других ячеек.
каждый вызов индуцирует ребро в графе.
каким образом считать всю инфу, пробежавшись по файлу лишь 1 раз?
на данный момент реализуется чтение за 2 прохода:
за 1 проход выясняем какие ячейки вообще есть и сколько под каждую нужно памяти, далее аллоцируем, далее второе чтение файла, записываем всю инфу, превращая ссылки на имена в ссылки на int (все структуры кладутся в массив, значит есть индекс, ссылку обязательно надо предствить в виде int+доп инфа типа смещение по х и у-это move {900 800})
инфа кладется в массив ячеек.
каждая ячейка хранит вызовы остальных ячеек.
будем считать, что ячейки могут быть такими большими, что в двойном экземпляре их нельзя держать в памяти...количество вызовов тоже очень большое...и кол-во ячеек очень большое.
ячейки нижнего уровня имеют вид:
cell 134 {
прямоугольник axb
}
таким образом дерево описывает геометрию, составленную из прямоугольников.
за 2 прохода все влезает в память.
за 1 проход первое, что лезет в ум-считываем всю ячейку, настраиваем calls корректно, аллоцируем нужную память, делаем копирование инфы в наш массив ячеек...и тд.
этот способ не пролазиит по памяти ;(
придумайте грамотный проход по файлу...