| Код |
|
))| Код |
|
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Оптимизация функции |
| Автор: vladko 14.4.2009, 11:18 | ||
Эта функция оформленная в виде длл считывает текстовый файл производит вычисления и выодит новый текстовый файл. Можно ли этот код оптимизировать по скорости? Например 150 мб считает минуту. Сократить бы это время в 2-3 раза...
|
| Автор: azesmcar 14.4.2009, 11:37 | ||||
| vladko ты хоть приведи код в порядок..а то читать это невозможно..коментарии добавь хоть какие-то, табуляцию не игнорируй. Добавлено через 3 минуты и 26 секунд vladko и этот код работает?
где free???
ты освободил два байта, обращаешся к большему количеству...или я чего-то не пойму? |
| Автор: GoldFinch 14.4.2009, 11:41 |
| жесть какая-то этот код не оптимизировать нада, а удалить и написать новый |
| Автор: vladko 14.4.2009, 11:45 |
| Блин, че так все плохо? На мелких файлах нормально работает... Код не я писал... |
| Автор: xvr 14.4.2009, 11:45 | ||||
Вот это
))
|
| Автор: zim22 14.4.2009, 11:45 |
| товарищ vladko уже эту тему подымал. http://forum.vingrad.ru/forum/topic-253997/anchor-entry1831844/0.html vladko, не лучше ли вам пойти в http://forum.vingrad.ru/forum/Vingrad-help-center.html? |
| Автор: vladko 14.4.2009, 11:46 |
| ага, только там не помогли... вот я и выложил результат помощи с другого форума... |
| Автор: GoldFinch 14.4.2009, 11:49 | ||
ололо помогли так помогли) |
| Автор: vladko 14.4.2009, 12:07 |
| да, помогли, а не флудили... прога рабочая... спасибо за исправления xvr!!! |
| Автор: 0xDX 14.4.2009, 12:09 |
| Читать файл нужно побольше буфером. Выделять память нужно залпом, и не когда не использовать malloc(new ) в цикле. |
| Автор: azesmcar 14.4.2009, 12:14 |
| vladko Если она работает - то это видимо счастливая случаность  1. Читай из файла большими кусками - например по мегабайту за итерацию. 2. Не выделяй память в цикле и не обявляй переменных. 3. Не забывай освобождать память если она больше не нужна. Попробуй все таки привести код в порядок.. |
| Автор: GoldFinch 14.4.2009, 12:19 |
| azesmcar, при завершении программы память освобождается сама, так что там ничего освобождать не надо |
| Автор: azesmcar 14.4.2009, 12:25 |
| GoldFinch на каждый вызов malloc и new должен быть free и delete соответственно до завершения программы. И не важно что операционная система подотрет за вами то что не сделали вы сами. |
| Автор: zim22 14.4.2009, 12:28 | ||
не получится. vladko писал: http://forum.vingrad.ru/index.php?showtopic=253997&view=findpost&p=1831824 |
| Автор: vladko 14.4.2009, 12:29 |
| azesmcar, а как читать блоками если файл разбит на строки (и они разной длины)? p.s. что зим, проще поржать, чем что-то посоветовать? |
| Автор: azesmcar 14.4.2009, 12:40 |
| vladko Скажи подробнее какой формат файла? Он у тебя вроде не текстовый. Что там запиасно и в какой очередности. Если я не ошибаюсь это long, long, double, int? сделай структуру с этими типами и читай через fread сразу в структуру, можно читать не по одному а блоками - по 20 структур к примеру, попытно пишешь в выходной файл. |
| Автор: GoldFinch 14.4.2009, 12:43 | ||
а почему они должны быть вы объяснить можете? или тупо заучили правило и теперь его повторяете? |
| Автор: vladko 14.4.2009, 12:45 |
| azesmcar, файл как раз текстовый, пример: 20090318 010017;1.4045;7 20090318 010150;1.405;1 20090318 010150;1.405;1 20090318 010151;1.405;1 20090318 010307;1.4049;1 20090318 010308;1.4044;1 20090318 010308;1.4041;1 20090318 010802;1.4049;1 20090318 011056;1.4046;1 20090318 011406;1.4047;1 20090318 011416;1.4047;1 20090318 011903;1.4049;2 20090318 011903;1.405;2 20090318 011912;1.4054;1 20090318 011912;1.4054;2 20090318 011912;1.4054;1 20090318 011926;1.4053;1 20090318 012141;1.4057;5 20090318 012159;1.4056;1 |
| Автор: azesmcar 14.4.2009, 12:53 |
| GoldFinch Если есть правило - оно обосновано! Очень интересует - создайте топик поговорим об этом. Тут другой вопрос обсуждается: Кратко для delte - чтобы вызывался деструктор для malloc - ос не обязана за вас это делать, нет стандарта ос который ее к этому обязывает, сегодня это виндоуз - завтра не дай и бог АбабОС - гарантий нет + это может быть только один модуль программы и по завершению функции - не факт что программа заканчивается. Добавлено через 3 минуты и 14 секунд GoldFinch это вам в голову не приходило или просто тупо думаете что виндоуз единственная операционная система и все программы состоят из одной единственной функции? Добавлено через 6 минут и 5 секунд vladko значит файл текстовый. Просто берем и читаем конкретный размер - к примеру 1мегабайт данных из файла в буфер выделенный malloc (выделяем один раз). Потом читаем из файла в этот буфер один мегабайт данных, смотрим сколько на самом деле прочитали (запоминаем). Обрабатываем данные в цикле, если нашли строку которая прочиталась наполовину, запоминаем ее начало - читаем продолжение из файла. Пока все данные не прочтем (т.е. сколько прочли - меньше чем сколько попросили прочесть) Примерно так |
| Автор: vladko 14.4.2009, 13:32 |
| azesmcar, да, спасибо, я понял что делать, а вот как... может быть в личке обсудим вариант взаимовыгодного сотрудничества? |
| Автор: azesmcar 14.4.2009, 13:38 |
| vladko напиши в аську минут через 10. Номер аськи в профайле |
| Автор: xvr 14.4.2009, 13:40 |
| Файл лучше даже не читать (пусть одним куском), а целиком замэпить в память (см. CreateFile/CreateFileMapping/MapViewOfFile), не забудьте затерминэйтить его нулем после мэпа. Для чтения данных из файла лучше применить не sscanf(fscanf) а прямой разбор через stroul/strtod (может быть быстрее) |
| Автор: GoldFinch 14.4.2009, 14:05 | ||
эта конкретная задача пишется под windows и состоит из одной единственной функции так зачем лепить код который в контексте этой конкретной задачи не нужен? |
| Автор: azesmcar 14.4.2009, 14:17 |
| GoldFinch затем что завтра - если программа станет делать что-то еще, разработчик забудет про malloc в функции proc1. Или это может быть другой разработчик который даже не знает что в функции proc1 есть malloc без free и разработчик надеялся на систему, в задаче нигде не указано что разработка идет под операционную систему виндоуз, это С++, и раздел называется С++ а не программирование под виндоуз, код надо писать так чтобы при портировании делалось минимум изменений (если можно вообще не делалось), т.е. писать в соответствии со стандартами. Я после института не писал ни одной программы которая бы отработала один раз и завершилась, в работе такие программы встречаются редко и освобождение памяти должно войти в привычку. |
| Автор: GoldFinch 14.4.2009, 14:21 | ||
в задаче сказано что это dll, значит windows. читайте задачу внимательнее |
| Автор: azesmcar 14.4.2009, 14:30 |
| GoldFinch хотите длл под линукс покажу  просто расширение другое..ладно, проехали...не хотите освобождать память - не надо. |
| Автор: GoldFinch 14.4.2009, 14:40 |
| azesmcar, судя по предыдущим постам длл пишется для использования в VBA, VBA под линукс покажете? |
| Автор: azesmcar 14.4.2009, 14:43 |
| GoldFinch предыдущий пост - это в другом топике? не смотрел. Какая разница какая операционка? я вам полно других примеров привел. Это вопрос из темы "не надо передавать std::string по константной ссылке, все равно в линуксе он 4 байта занимает". |
| Автор: mes 14.4.2009, 16:08 |
| GoldFinch, я Вас правильно понял, Вы утверждаете, что если пишите короткую прогу и знаете что под Виндоус, то предпочтительней или даже необходимо не возвращать выделенную память ?! |
| Автор: J0ker 14.4.2009, 16:22 |
| GoldFinch, вы строите из себя панка от программирования? у вас, должен заметить, это получается правда в нехорошем смысле слова "панк" |
| Автор: zim22 14.4.2009, 16:54 | ||
почитал словарь Collins. У панка одни положительные значения за исключением двух: 1) obsolete a young male homosexual; catamite 2) obsolete a prostitute J0ker, вы какое имели ввиду? |
| Автор: vinter 14.4.2009, 17:11 |
| zim22, Punk - падонок(в современном мире так называют людей, которые пытаются выделится среди других своим идиотизмом) |
| Автор: J0ker 14.4.2009, 17:12 | ||
http://www.urbandictionary.com/define.php?term=punk http://www.merriam-webster.com/dictionary/punk a usually petty gangster, hoodlum, or ruffian |
| Автор: zim22 14.4.2009, 17:25 | ||||
улыбнуло.
|
| Автор: GoldFinch 14.4.2009, 17:51 |
| mes, предпочтительней или даже необходимо не писать код который производит ненужные действия, (особенно не приносящие пользы, увеличивающие время написания программы, увеличивающие объем бинарника программы, снижающие быстродействие программы) |
| Автор: mes 14.4.2009, 18:15 | ||
в принципе согласен..но способ достижения я выбрал бы другой, В грубом изложении я согласен отказаться от delete (речь веду о С++ ), но не в пользу брошенного без присмотра объекта, а в передачи прав на его удаление умному указателю. В общем всегда стараюсь придерживаться правила: функция не знает o том, в каком контексте она работает. Вы же, насколько я смог представить по Вашим постам, стараетесь нагрузить свою память лишними деталями. В частности применительно к последним высказываниям, заставляете себя постоянно помнить в какой из функций хватает, а в какой не поставили освобождение памяти. Хотя гораздо легче просто писать симметрично. |
| Автор: J0ker 14.4.2009, 18:37 | ||
безусловно т.е. теперь вы согласны, что уничтожать объекты и освобождать память необходимо? |
| Автор: azesmcar 14.4.2009, 18:38 | ||
Предпочтительней и даже необходимо писать код который будет читабельным и понятным. Преждевременная оптимизация - зло! Программу можно оптимизировать сменив алгоритм, перейдя с С++ на С, в крайнем случае можно еще поизвращатся если нужно очень быстро - и это основные методы оптимизации. А не освобождать память это не то что преждевременная оптимизация, это почти доходит до маразма. Насколько вы повысите произодительность программы убрав delete или free? Просто посчитайте и вы поймете что оно того не стоит. Добавлено через 2 минуты и 16 секунд А насчет лишних действий - любая вызванная вами функция в той или иной степени выполняет что либо что возможно на первый взгляд вам и не нужно. Если хотите чтобы код делала только то что вы от него требуете и ничего более - единственный выход писать на ассемблере. |
| Автор: GoldFinch 14.4.2009, 20:07 | ||
такой же код пишется и на С++ и на дельфи, я хз что вы так уперлись в ассемблер |
| Автор: Lazin 14.4.2009, 20:33 |
| а что этот код должен делать? |
| Автор: J0ker 14.4.2009, 21:13 | ||
не прикидывайтесь неджедаем |
| Автор: sdukshis 14.4.2009, 22:00 |
| Если я правильно понял программу, то в ней важно, чтобы данные переписались в новый файл уже в отсортированном виде. Для этого Вы организуете считывание в map, который являясь упорядоченным деревом производит сортировку. Или возможно Вам нужно исключить или обработать повторяющиеся данные В первом случае лучше считывать данные в структуру типа vector (с заранее выделенной памятью) или list(хотя если можно заранее оценить размер данных, то лучше vector), а сортировку производить стандартными алгоритмами. Во втором случае все тоже самое, только обрабатывать дубликаты опять с помощью стандартных функций. Вообще очень советую разбить программу на подпрограммы и произвести профилирование кода. Там сразу выплывет, какая часть кода занимает основное время. |
| Автор: zim22 15.4.2009, 07:03 | ||||
зачем память заранее выделять? вектор умный - сам выделит и зарезервирует в придачу.
если под сортировкой вы подразумеваете алгоритм sort из <algorithm>, то list в пролёте. у него BiDirrectional Iterators, а не RandomAccess. Хотя у list и есть встроенная функция-член sort, но мне кажется она работает медленнее, чем sort из <algorithm> |
| Автор: vinter 15.4.2009, 08:02 | ||||
если не выделить самостоятельно будут overheads
у них одинаковая сложность |
| Автор: GoldFinch 15.4.2009, 08:17 | ||
если написано что сложность O(N*log(N)) это может значить что в одном случае N*log(N) а в другом 100*N*log(N) |
| Автор: zim22 15.4.2009, 08:33 | ||
насколько я знаю в O-нотации указывается верхняя граница сложности алгоритма. Т.е. гарантированно алгоритм выполниться за масимумум N*log(N) шагов |
| Автор: vinter 15.4.2009, 09:27 | ||
с чего бы это? |
| Автор: Lazin 15.4.2009, 09:41 | ||
ну а почему мы обычно используем quik sort вместо merge sort? |
| Автор: vinter 15.4.2009, 09:57 |
| Lazin, я тебя не понял, у алгоритма есть заявленная сложность. С чего бы ей увеличиваться? |
| Автор: Lazin 15.4.2009, 10:09 |
| О оценка, это еще не все, что можно сказать о сложности алгоритма к примеру, quick sort имеет сложность O(N*log N) в большинстве случаев, а в худшем случае O(N*N), а у bucket sort сложность - O(N), но константа перед этим N и большее использование памяти приводят к тому, что он работает медленнее чем обычный quick sort в большинстве случаев  |
| Автор: sdukshis 15.4.2009, 13:30 | ||||||
Проблему выбора между vector и list я вижу в следующем: Оба эти контейнера умеют динамически увеличиваться в размере, но делают это по разному. размер Vector растет как степень двойки, но при этом ему нужно осуществлять копирование элементов в новый участок памяти. Поэтому если можно как-то оценить (я не говорю о точном кол-ве) размер входных данных, то можно pапросить выделение памяти всего 1 раз. контейнер list запрашивает новую память при добавлении каждого элемента. Отсюда и моё предложение, что лучше использовать vector если можно представить размер входных данных(например размер файла/среднюю длину строки). Кроме того сортировка для vector может быть выполнена быстрее чем для list (может алгоритмическая сложность у них и одинакова, но просто попробуйте замерить на достаточно большом объёме данных, разница должна хорошо просматриваться). Поиск повторений для обоих контейнеров примерно одинаковый, так что я за использование vector |
| Автор: zim22 15.4.2009, 13:36 | ||
полностью с вами соглашусь. |
| Автор: GoldFinch 15.4.2009, 18:25 |
| zim22, vinter, вы перед тем как пользоваться умным математическим понятием порядка сложности, O[f(N)] узнали бы что это означает. Конечно труъ программистам математика наверное не нужна, но бездумно пользоваться терминами тоже не хорошо. какбэ фраза "сложность алгоритма имеет порядок O[g(N)]" означает что для функции сложности f(N) существует такая окрестность точки n при которой при N->n отношение f(x)/g(x) ограничено в других определениях можно найти варианты "предел f(x)/g(x) при N->n существует и не равен нулю" или "... при N стремящемся к бесконечности ..." так вот это значит что 10*N = O[100*N] а также значит что может существовать m, такое что при N<m O[N*N]<O[N], что вобщем-то очевидно, если представить график параболы y=x*x и прямой y=x для x<1 |
| Автор: vinter 15.4.2009, 18:57 | ||||
отлично, но у нас нет никаких констант. Есть четкая верхняя граница.
интересный экскурс, только причем он тут? O() это верхняя граница числа операций, которые могут быть пороизведены в данном алгоритме. И не надо никаких констант дописывать, туда, где их нет. |
| Автор: Lazin 15.4.2009, 19:08 |
| lol |
| Автор: zim22 15.4.2009, 19:24 | ||
http://en.wikipedia.org/wiki/Big_O_notation
|
| Автор: GoldFinch 15.4.2009, 19:37 | ||
а O(1) это наверное 1 операция? на самом деле, это k операций, при этом k не зависит от N zim22, "on the growth rate", вы понимаете разницу между самой функцией и ее производными? скорость возрастания, это функция полученная из функции сложности, и в выражении O[g(N)] - g(N) это ее верхняя асимптотическая граница |
| Автор: vinter 15.4.2009, 19:43 | ||
GoldFinch, OMG ты читай, что тебе пишут, а не то что ты хочешь читать. Я тебе еще раз повтаряю сложность это ВЕРХНЯЯ ГРАНИЦА.
где разночтение с моими словами или zim22? |
| Автор: GoldFinch 15.4.2009, 19:50 |
| vinter, верхняя граница чего? если алгоритм содержит 100*N операций, то его сложность O(N), а если он содержит 10*N операций, то его сложность тоже O(N) и если алгоритм содержит 100000+N операций, его сложность тоже O(N), потому что предел отношения (100000+N)/N при N стремящемся к бесконечности конечен и не равен нулю, тоже самое и с пределом (10*N)/(100*N) |
| Автор: vinter 15.4.2009, 20:04 | ||
GoldFinch, дык, константа не зависит от N, естественно. Но в конкретном прмере не было никаких констант. Была конкретная сложность. Прямым текстом:
Вот, все. После чего ты начал приплетать, какие то левые константы, которые вообще не имеют отношения к конкретной сложности... |
| Автор: GoldFinch 15.4.2009, 20:12 |
| vinter, изначально разговор был о том, что у разных алгоритмов при одинаковой сложности O[g(N)] может быть разное время выполнения |
| Автор: vinter 15.4.2009, 20:22 |
| GoldFinch, твоя правда. |
| Автор: J0ker 15.4.2009, 22:09 |
| сложность алгоритма сортировки показвает изенение времени выполнения при изменении n прямого отношения к сравнению алгоритмов между собой это не имеет |
| Автор: vinter 16.4.2009, 05:26 | ||
понятие сложнсти было придумано,как раз для сравнения алгоритмов. Так, что имеет. |
| Автор: J0ker 16.4.2009, 16:26 | ||||
я сазал прямого отношения big O между алгоритмами можно сравнивать исключительно после обсуждения сложности итерации и понятие сложности было придумано в первую очередь для указания отношния времени выполнения к n |
