Здравствуйте, Pavel Dvorkin, Вы писали:
PD>400 Мб. PD>Понял теперь, куда я веду ?
Упс! Я занял аж целых 10% оперативной памяти на моей рабочей машине!
PD>Пока что решения нет. У меня дополнительных 500 Мб не имеется.
К порядку! Во вводной небыло сказано, что мы считаем, будто бы сейчас 2000-й год.
Так дело не пойдет. Сейчас вы решаете мою задачу с той же степенью конкретизации, что и я вашу. А там видно будет.
PD>Все ясно. Вместо программы я должен заказчику представить асимптотический анализ сложности алгоритмов и расходов памяти.
Я не ваш заказчик. Не нужно соскальзывать с темы. Мы говорим о том, что подразумевается под словами "И рекламировать их все-равно что рекламировать супер оптимизированную написанную на ассемблере сортировку пузырьком." Я вам все пытаюсь втолковать про асимптотическую сложность — только это все пролетает у вас мимо ушей и вы продолжаете заливаться соловьем про подсчет битов. Результат такого подхода может заказчика здорово огорчить.
PD>А ведь я именно задачу на парсинг и представил.
В этой задаче не требуется парсить строки — требуется парсить поток символов.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[46]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, AndrewVK, Вы писали:
K>>А, ну понятно, вы сейчас будете ждать, пока я подсчитаю все биты до последнего. AVK>Не, все намного смешнее. Он скажет, что у него нет времени на всякую ерунду. Мы это уже проходили.
Да я, в общем-то, прочел тут не подин подобный диспут, да и сам участвовал — т.е. в принципе понимаю, что будет дальше и с кем я имею дело. И даже читая чужие аналогичные диспуты, порой, удивляюсь — зачем же человек ведет их без всякой перспективы? Но, случается, что что-то накатывает на меня и я опять, снова ввязываюсь в спор. Рационального объяснения для моих действий — увы — нет.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[47]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, Klapaucius, Вы писали:
K>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>400 Мб. PD>>Понял теперь, куда я веду ?
K>Упс! Я занял аж целых 10% оперативной памяти на моей рабочей машине!
Упс не упс, а условия надо либо соблюдать, либо не браться за задачу.
PD>>Пока что решения нет. У меня дополнительных 500 Мб не имеется.
K>К порядку! Во вводной небыло сказано, что мы считаем, будто бы сейчас 2000-й год.
Во вводной было ясно сказано
PD>На вспомогательные структуры, так и быть, еще 50-70 Мб дам.
Если не можешь этому требованию удовлетворить — не берись. А почему — это мое дело. Это не упражнение, а часть реальной задачи, и там еще много чего другого есть.
K>Так дело не пойдет. Сейчас вы решаете мою задачу с той же степенью конкретизации, что и я вашу. А там видно будет.
Пока я упорно не вижу никакого решения , удовлетворяющего моим требованиям. Свое выложу на той неделе.
PD>>Все ясно. Вместо программы я должен заказчику представить асимптотический анализ сложности алгоритмов и расходов памяти.
K>Я не ваш заказчик.
Это верно. И слава богу. Но я с самого начала сказал, что это не учебное упражнение, а часть моей реальной задачи. Я должен либо ее сделать и уложиться в требования, либо признать, что не могу сделать. И это я должен сказать заказчику. Одно из двух.
>Не нужно соскальзывать с темы. Мы говорим о том, что подразумевается под словами "И рекламировать их все-равно что рекламировать супер оптимизированную написанную на ассемблере сортировку пузырьком." Я вам все пытаюсь втолковать про асимптотическую сложность — только это все пролетает у вас мимо ушей и вы продолжаете заливаться соловьем про подсчет битов. Результат такого подхода может заказчика здорово огорчить.
Ему безразлична асимптотическая сложность. Ему работающую программу надо. За асимпотоику он мне деньги платить не будет, а за программу. что я сделал — заплатил.
K>В этой задаче не требуется парсить строки — требуется парсить поток символов.
На здоровье. Можешь парсить поток символов, если тебе больше нравится такое определение. Только решение в студию!
With best regards
Pavel Dvorkin
Re[47]: Зачем нужны циклы если есть рекурсивные функции
K>Да я, в общем-то, прочел тут не подин подобный диспут, да и сам участвовал — т.е. в принципе понимаю, что будет дальше и с кем я имею дело. И даже читая чужие аналогичные диспуты, порой, удивляюсь — зачем же человек ведет их без всякой перспективы?
Да, очень красиво. Если решения дать не можешь, то надо перейти на личности. Печально.
With best regards
Pavel Dvorkin
Re[48]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Это не упражнение, а часть реальной задачи
Это умозрительное уражнение с высосанными из пальца граничными условиями. У моего упражнения — высосанных из пальца граничных условий нет — да еще и к предмету разговора упражнение имеет непосредственное отношение, чего о вашем не скажешь. Если мне в реальности заказчик поставит задачу написать велосипедную базу данных — я честно постараюсь его убедить что для такого объема есть базы данных и даже бесплатные — я не настолько стеснен в средствах чтобы наживаться на чужих слезах. В том случае, если он будет настаивать — я, пожалуй, отойду подальше, а то вдруг заказчик меня за ногу укусит, а мне потом уколы ставить в живот?
PD>Пока я упорно не вижу никакого решения , удовлетворяющего моим требованиям.
Ну ладно — допустим это моя проблема. Но я бы все-таки хотел задачу, которая имеет отношение к обработке строк.
PD>Свое выложу на той неделе.
Ура!
PD>Я должен либо ее сделать и уложиться в требования, либо признать, что не могу сделать. И это я должен сказать заказчику.
А почему заказчик не хотел пользоваться базой данных?
PD>Ему безразлична асимптотическая сложность. Ему работающую программу надо. За асимпотоику он мне деньги платить не будет, а за программу. что я сделал — заплатил.
Это демагогия. Если вам платят деньги за производительность — то в первую очередь это плата за асимптотическую сложность — а во вторую — за полировку битов.
PD>На здоровье. Можешь парсить поток символов, если тебе больше нравится такое определение. Только решение в студию!
Вы во второй раз уже, фактически, признали, что к теме это отношения не имеет. Зачем мне тогда ее решать? Вернее зачем я ее уже решил?
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[48]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, Klapaucius, Вы писали:
K> И даже читая чужие аналогичные диспуты, порой, удивляюсь — зачем же человек ведет их без всякой перспективы?
Некоторые паталогически не способны признать свою неправоту. Это очень хорошо видно, когда человек под конец начинает говорить горы абсурда, либо сваливается на грубую демагогию и хамство.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237 on Windows 7 6.1.7100.0>>
Здравствуйте, Klapaucius, Вы писали:
K>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Это не упражнение, а часть реальной задачи
K>Это умозрительное уражнение с высосанными из пальца граничными условиями.
Мне за него деньги заплатили. Это раз. Во-вторых, если уж так — надо было сразу сказать, а не пытаться решать.
>У моего упражнения — высосанных из пальца граничных условий нет — да еще и к предмету разговора упражнение имеет непосредственное отношение, чего о вашем не скажешь. Если мне в реальности заказчик поставит задачу написать велосипедную базу данных — я честно постараюсь его убедить что для такого объема есть базы данных и даже бесплатные — я не настолько стеснен в средствах чтобы наживаться на чужих слезах.
Данные представлены из источника, который мне передать не могут. Причины обсуждать здесь не будем. Мне представлен текстовый файл в формате CSV. У меня нет оснований отказаться от его обработки.
PD>>Пока я упорно не вижу никакого решения , удовлетворяющего моим требованиям.
K>Ну ладно — допустим это моя проблема.
Это надо понимать как отказ от попыток найти решение ? Если да — выложу свое (не сегодня). Если нет — жду продолжения.
>Но я бы все-таки хотел задачу, которая имеет отношение к обработке строк.
А это и есть задача на парсинг текстового файла. А он, как всем известно, состоит из строк. Независимо от того, как они представлены — в виде char*, string всех сортов или же заканчиваются CR/LF. В CSV файле лежат текстовые строки, а это задача на их обработку.
PD>>Свое выложу на той неделе.
K>Ура!
PD>>Я должен либо ее сделать и уложиться в требования, либо признать, что не могу сделать. И это я должен сказать заказчику.
K>А почему заказчик не хотел пользоваться базой данных?
См. выше.
PD>>Ему безразлична асимптотическая сложность. Ему работающую программу надо. За асимпотоику он мне деньги платить не будет, а за программу. что я сделал — заплатил.
K>Это демагогия. Если вам платят деньги за производительность — то в первую очередь это плата за асимптотическую сложность — а во вторую — за полировку битов.
Асимптотика совершенно была неинтересна. Эти данные такие, как они есть, и в будущем объем этих данных может увеличиться не более чем на 5-10%. Поэтому мне надо было сделать именно с существующим файлом, ну и предусмотреть возможность, что он будет слегка побольше когда-нибудь. Меньше он стать не может. Больше даже в 1.5 раза он быть не сможет. По крайней мере в 21 веке .
K>Вы во второй раз уже, фактически, признали, что к теме это отношения не имеет. Зачем мне тогда ее решать? Вернее зачем я ее уже решил?
Решение, не удовлетворяющее требованиям, не есть решение. Неужели это надо объяснять ?
With best regards
Pavel Dvorkin
Re[48]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, AndrewVK, Вы писали:
PD>>Плохой из тебя предсказатель. Даже прошлое предсказывать не умеешь.
AVK>Это не предсказание, это констатация факта.
Твое сообщение (преддыдущее) от 18:00, а мой ответ был дан в 17:32
Здравствуйте, Klapaucius, Вы писали:
PD>>Если решения дать не можешь, то надо перейти на личности. Печально.
K>О чем это вы? Я тут, вообще говоря, обсуждал и осуждал только весьма несовершенную свою собственную личность.
>т.е. в принципе понимаю, что будет дальше и с кем я имею дело.
Выделенное тоже относится к твоей собственной несовершенной личности или же нет ?
With best regards
Pavel Dvorkin
Re[49]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ладно. Давай закончим пустые рассуждения. Вот тебе конкретная задача. Я ее не выдумал, это (с небольшими модификациями) то, что мне реально пришлось делать.
Как верно заметил Klapaucius эта задача абсолютно не релевантна обработке строк.
Но чтобы ты перестал гнуть пальцы веером я тебе ее решу.
Но после этого ты решишь задачу которую поставил Klapaucius.
PD>Дан файл в формате CSV. 10 полей на строчку, есть пустые поля. Поля не длинные, обычно 5-10 символов. Количество строк известно, порядка 5 миллионов. Размер файла 200 Мб, известен точно.
Если у нас есть гарантия что общая длинна строки не может быть больше 255 байт то мы делаем следующее преобразование:
Превращаем каждую строку исходного файла в структуру вида:
Первый байт суммарная длинна полей. Следующие 9 байт начала полей с второго по 10ое. Начало первого мы знаем.
Далее идут поля без разделителей.
Очевидно что мы заняли ровно столько же памяти сколько занимал исходный CSV. А если в CSV использовались двухбайтовые переводы строк то мы еще и 5 метров сэкономили. А если там были заэскейпленные поля то еще больше.
Попутно собираем массив смещений структур.
Далее делаем еще 2 копии этого массива и сортируем все 3 массива по соответствующему полю.
PD>1. Выдачу этих строк в исходном порядке
Бежим по структуре и...
PD>2. Выдачу строк, отсортированых по любому из первых трех полей. (SELECT * ORDER BY FIELD1)
Бежим по соответствующему индексу...
PD>3. Выдачу любого набора полей в любом порядке из строк, отсортированных по любому из первых трех полей (SELECT FIELD2,FIELD5 ORDER BY FIELD1)
Бежим по соответствующему индексу, а выдачу полей по вышеописанной структуре я думаю ты сам осилишь.
PD>4. Выдачу аналогично п.3, но только для тех строк, у которых поле сортировки равно чему-то (SELECT FIELD2,FIELD5 ORDER BY FIELD1 WHERE FIELD1="ABCD")
Двоичным поиском находим начало и конец соотвествующего интервала в нужном нам индексе. Далее см пункт 3.
PD>Можешь завести нужные вспомогательные структуры, массивы и т.п, но копировать строки не разрешается. Иными словами, каждая исходное текстовое поле должно присутствовать в памяти ТОЛЬКО ОДИН РАЗ. Хоть явно, хоть неявно. На вспомогательные структуры, так и быть, еще 50-70 Мб дам.
Итого +60М на 3 индекса -мусор из SCV.
Заметь твои любимые asciiz строки не понадобились. Более того на всех этапах у нас всегда известна длинна строки.
Твоя очередь.
Очень хочется увидеть решение на asciiz строках
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[46]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>При таких условиях на каждый из этих блоков получается не более чем по 1, от силы 2 байта. А на блок надо хоть ссылку, хоть указатель оформить. А ее (его) размер 4 байта.
Для "указателя" достаточно полбайта.
Поля не длинные, обычно 5-10 символов
PD>А длину блока хранить будем ?
Нет необходимости, можно вычислять как разницу "указателей".
PD> Если в формате, как в string, то это еще 4 байта, итого 8. 8 байт на 50 миллионов полей — 400 Мб.
25Мб вроде выходит?
.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Re[50]: Зачем нужны циклы если есть рекурсивные функции
PD>Дан файл в формате CSV. 10 полей на строчку, есть пустые поля. Поля не длинные, обычно 5-10 символов. Количество строк известно, порядка 5 миллионов. Размер файла 200 Мб, известен точно.
PD>Делай что хочешь, но должен обеспечить
PD>2. Выдачу строк, отсортированых по любому из первых трех полей. (SELECT * ORDER BY FIELD1) PD>3. Выдачу любого набора полей в любом порядке из строк, отсортированных по любому из первых трех полей (SELECT FIELD2,FIELD5 ORDER BY FIELD1) PD>4. Выдачу аналогично п.3, но только для тех строк, у которых поле сортировки равно чему-то (SELECT FIELD2,FIELD5 ORDER BY FIELD1 WHERE FIELD1="ABCD")
PD>Для п.2-4 сортировка в момент запроса не допускается. Данные должны быть готовы для выдачи в этот момент без какой бы то ни было модификации.
PD>Вся информация должна быть в ОП, чтение из файла можно провести только один раз. PD>Можешь завести нужные вспомогательные структуры, массивы и т.п, но копировать строки не разрешается. Иными словами, каждая исходное текстовое поле должно присутствовать в памяти ТОЛЬКО ОДИН РАЗ. Хоть явно, хоть неявно. На вспомогательные структуры, так и быть, еще 50-70 Мб дам.
Заводим буфер длиной на 1 байт больше чем размер файла. Читаем файл в буфер целиком в двоичном виде.
Заводим три массива указателей p1,p2,p3 размером в количество строк (оно известно)
Проходим по буферу, заменяем запятые на нули. В конце строки нет запятой, но есть CR/LF. CR заменяем на 0, LF игнорируем.
(Осторожно! В самом конце файла может CR/LF не быть. Именно поэтому я задал буфер на 1 байт больше. Если это так, записываем 0 в конце)
По ходу этого прохода формируем массив p1 как массив указателей на начала строк как они были (и есть)
Копируем p1 в p2 и p3
Сортируем p1 , используя в качестве ключа первое текстовое поле. Там asciiz, так что используем стандартные qsort и strcmp
Сортируем p2 по второму, и p3 по третьему полю таким же образом. Поскольку у нас строки заканчиваются нулем, переход от одного поля к другому не вызывает проблем. Фактически мы здесь имеем почти multi-sz формат, только без завершающего нуля.
PD>1. Выдачу этих строк в исходном порядке
Пройти буфер подряд без использования этих указателей
PD>2. Выдачу строк, отсортированых по любому из первых трех полей. (SELECT * ORDER BY FIELD1)
Пройти буфер в порядке p1, p2 или p3
PD>3. Выдачу любого набора полей в любом порядке из строк, отсортированных по любому из первых трех полей (SELECT FIELD2,FIELD5 ORDER BY FIELD1)
Аналогично 2, но выбирать только нужные поля.
PD>4. Выдачу аналогично п.3, но только для тех строк, у которых поле сортировки равно чему-то (SELECT FIELD2,FIELD5 ORDER BY FIELD1 WHERE FIELD1="ABCD")
Провести двоичный поиск в массиве p1, p2 или p3 соответственно, найти начало и конец участка, соответствующего требуемому полю сортировки, далее аналогично 3.
Задача решается для любого размера как исходных строк, так и полей.
With best regards
Pavel Dvorkin
Re[43]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, Pavel Dvorkin, Вы писали:
WH>Но после этого ты решишь задачу которую поставил Klapaucius.
Непременно. Я уж решение сделал, но выложу либо сегодня попозже, либо завтра.
PD>>Дан файл в формате CSV. 10 полей на строчку, есть пустые поля. Поля не длинные, обычно 5-10 символов. Количество строк известно, порядка 5 миллионов. Размер файла 200 Мб, известен точно. WH>Если у нас есть гарантия что общая длинна строки не может быть больше 255 байт
Нет такой гарантии. В условиях ничего об этом не сказано.
WH>Твоя очередь. WH>Очень хочется увидеть решение на asciiz строках
Здравствуйте, Pavel Dvorkin, Вы писали:
GN>>Для "указателя" достаточно полбайта.
Поля не длинные, обычно 5-10 символов
PD>Обычно Сильно рискуешь.
Применяя Хаффмана, или арифметическое кодирование?
.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
