![]() |
Здравствуйте, гость ( Вход | Регистрация )
![]() ![]() |
![]() |
![]()
Сообщение
#121
|
|
![]() 😸🧡✊✌️ Сообщений: 16 396 Спасибо сказали: 3231 раз ![]() |
Понял в чем непонятка!
![]() "Данные не помещаются в оперативную память!" - это по-английски "The data don't fit the RAM", а не "The data aren't placed to the RAM" То есть, по-русски, оперативки не хватает. ![]() А кешировать лучше сразу две строки (чтобы иметь возможность их сравнивать, как-то так), так что как минимум два буфера. ![]() -------------------- Я слежу за тобой!
![]() ![]() Цитата Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел. Борис "Бонус" Репетур, "От винта!", выпуск 38. |
|
|
![]()
Сообщение
#122
|
|
![]() •●Revolucionario●• Сообщений: 2 467 Спасибо сказали: 5936 раз ![]() |
Ну, для одиночного сравнения каждой записи хватит и единственного буфера с эталонной строкой, а массовое слабо применимо, если даже (цитирую) "одна запись потенциально тоже не помещается" .
-------------------- life MOV.I #life+1, *life
האם יש זמן לעצור ? |
|
|
![]()
Сообщение
#123
|
|
![]() 😸🧡✊✌️ Сообщений: 16 396 Спасибо сказали: 3231 раз ![]() |
Сравниваем одну запись с другой, обе в память целиком быть загружены потенциально не могут, обе могут находиться в разных секторах файла. Разумеется, обе записи надо частично загрузить в память, сравнить их начала, если начала совпадают, продолжить загрузку и сравнение, пока не будет найдено первое отличие. Такие дела. Да, еще вначале надо как-то позиционироваться на начало записи.
Вначале нужно вывести минимальную строку, затем вторую по величине, затем третью и т.д. до максимальной. Причем это нужно сделать, не создавая дополнительных файлов и не изменяя исходный. И еще одна мысль: файл можно открыть два раза (получить два хендла), тогда можно немного упростить работу с текущей позицией. -------------------- Я слежу за тобой!
![]() ![]() Цитата Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел. Борис "Бонус" Репетур, "От винта!", выпуск 38. |
|
|
![]()
Сообщение
#124
|
|
![]() •●Revolucionario●• Сообщений: 2 467 Спасибо сказали: 5936 раз ![]() |
Цитата Разумеется, обе записи надо частично загрузить в память, сравнить их начала, если начала совпадают, продолжить загрузку и сравнение, пока не будет найдено первое отличие. Именно, но статические буферы для хранения этих фрагментов не требуются - их вполне можно подержать на стеке, все равно ведь содержимое будет постоянно разрушаться при дозагрузке. Цитата Причем это нужно сделать, не создавая дополнительных файлов и не изменяя исходный. А где сказано, что нельзя использовать дополнительные файлы ? -------------------- life MOV.I #life+1, *life
האם יש זמן לעצור ? |
|
|
![]()
Сообщение
#125
|
|
![]() 😸🧡✊✌️ Сообщений: 16 396 Спасибо сказали: 3231 раз ![]() |
Ну, с дополнительным файлом получается вообще легко: создать индексный файл, с записями фиксированного размера, включающими: номер записи исходного файла и смещение от начала файла до начала записи, а затем отсортировать его по возрастанию содержимого записей.
После этого, последовательно проходя по индексу, обработать все записи. (Все нормальные СУБД так делают! ![]() -------------------- Я слежу за тобой!
![]() ![]() Цитата Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел. Борис "Бонус" Репетур, "От винта!", выпуск 38. |
|
|
![]()
Сообщение
#126
|
|
![]() Immortal Сообщений: 397 Спасибо сказали: 20 раз ![]() |
Цитата 21.06.2009 18:58:34, Chrono Syndrome
На сей раз просто техническая полемика. 21.06.2009 18:58:48, Chrono Syndrome Да я и согласилась уже почти. 21.06.2009 18:59:36, I am с чем 21.06.2009 18:59:47, I am дф2 уже уныл чуть более чем полностью 21.06.2009 18:59:55, I am в этом помогла мышиная возня ХоТа 21.06.2009 19:00:03, I am из за которой набежало тысячи школоты 21.06.2009 19:01:32, Chrono Syndrome http://forum.df2.ru/index.php?act=ST&f=83&t=8575&st=120 21.06.2009 19:10:27, I am сортировка большого файла иначе делается 21.06.2009 19:10:54, Chrono Syndrome Как ? 21.06.2009 19:11:38, I am ну вкратце делаем так берем шмат файла например в 200мег кидаем в память сортируем пишем на диск в 1ый файл второй шмат также сортируем пишем на диск в 2ой файл и т.д. 21.06.2009 19:11:53, Chrono Syndrome Так. Дальше что ? 21.06.2009 19:12:00, I am после этого сливаем эти куски для этого нам надо 2*Н записей строк 21.06.2009 19:12:17, Chrono Syndrome Ну, слили. 21.06.2009 19:12:28, Chrono Syndrome У нас естьф аргментально остортиврованный файл. 21.06.2009 19:13:02, I am Х(номер файла,0) = значение из текушей строки файла Х(номер файла,1) = значение из следуший за текушей строкой файла и еще храним номер этой самой строки 21.06.2009 19:13:32, I am вот и сравнивая между собой каждые строчки сдвигаем счетчики строк в каждом куске 21.06.2009 19:13:43, I am итого при слдиянии выйдет что большой файл сортирован 21.06.2009 19:14:18, Chrono Syndrome Хм... 21.06.2009 19:14:25, Chrono Syndrome Интнрестная методика. 21.06.2009 19:14:29, I am 21.06.2009 19:12:28, Chrono Syndrome У нас естьф аргментально остортиврованный файл. хитрым слиянием 21.06.2009 19:14:30, Chrono Syndrome *Интерестная. 21.06.2009 19:14:43, I am не тупо дописывая в конец 21.06.2009 19:15:02, I am а среди этих Н записей находим минимальную она будет первой строкой в итоговом файле 21.06.2009 19:15:17, I am в Н ом куске где мы ее нашли сдвинули счетчик строки на еденичку 21.06.2009 19:15:27, I am снова находим минимальное 21.06.2009 19:15:42, I am где нашли пишем в итоговый файл еще строку сдвигаем на еденичку 21.06.2009 19:15:54, I am а естть еще более хитрые методики 21.06.2009 19:16:00, I am там как раз оба поля можно учитывать 21.06.2009 19:16:09, I am но чем проще алг тем меньше в нем ошибок ![]() 21.06.2009 19:16:17, Chrono Syndrome Логично). 21.06.2009 19:16:22, I am короче все просто как 5 копеек обосцать 21.06.2009 19:16:59, I am главное чтобы школота не забыла что все куски надо сортировать одним и тем же методом по которому нам нужен отсортированный итог ![]() 21.06.2009 19:17:33, I am минус тока один на временные файлики нам нужна ТЕМП папка в размере исходного файла 21.06.2009 19:17:44, Chrono Syndrome Разумеется. 21.06.2009 19:18:12, I am ну и при диком желании уж операции чтения из кусков мона кешировать блоками по Н кб чтобы винт не убивать ![]() 21.06.2009 19:18:56, I am передавай школоте привед ![]() 21.06.2009 19:19:08, Chrono Syndrome ![]() 21.06.2009 19:19:18, Chrono Syndrome Можешь запостить алгоритм). 21.06.2009 19:19:28, I am скопипасть я не против 21.06.2009 19:19:32, Chrono Syndrome Только приведи его в понятный школоте вид). 21.06.2009 19:19:45, I am тока из копипаста строку "школоте привед" не удаляй 21.06.2009 19:19:54, Chrono Syndrome ))) 21.06.2009 19:20:02, Chrono Syndrome Ладно, если ничего не предложат -запощу. 21.06.2009 19:20:39, I am ye yt [ji z cfv crjgbgfcn. 21.06.2009 19:20:49, I am ну не хош я сам скопипащю 21.06.2009 19:20:59, Chrono Syndrome Скопипасть). -------------------- Браво, сударь, браво!
|
|
|
![]()
Сообщение
#127
|
|
![]() 😸🧡✊✌️ Сообщений: 16 396 Спасибо сказали: 3231 раз ![]() |
Идея супер! Признавайтесь, проверка четности целого числа поиском по двум базам данных тоже принадлежит вам?
-------------------- Я слежу за тобой!
![]() ![]() Цитата Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел. Борис "Бонус" Репетур, "От винта!", выпуск 38. |
|
|
![]()
Сообщение
#128
|
|
![]() Immortal Сообщений: 397 Спасибо сказали: 20 раз ![]() |
Цитата(tolich @ 21 Jun 2009, 20:03) Идея супер! Признавайтесь, проверка четности целого числа поиском по двум базам данных тоже принадлежит вам? создание подобных предрасчитанных таблиц вполне имеет смысл например помнитсься в 2000 винде хеш пароля не привязан к аппаратной части а только к паролю потому однажды созданная реверсная база размером кажется на 8 гигабайт давала в течение пару минут пасс от хеша. ![]() и да работа с винтом вполне нормальное явление не надо его стеснятся тем более когда память ограниченна 90% выших хитрых вариантов будут медленней чем обычное решение "в лоб" -------------------- Браво, сударь, браво!
|
|
|
![]()
Сообщение
#129
|
|
![]() 😸🧡✊✌️ Сообщений: 16 396 Спасибо сказали: 3231 раз ![]() |
Напомню задачу:
Цитата(DracoLich @ 16 Jun 2009, 14:47) Нужно сортировать список из файла, не изменяя в конечном итоге файл. Число записей в файле неограниченно (теоретически), поэтому заносить в массив не получается. Подскажите, как можно реализовать сортировку налету. Язык С++ То что вы предлагаете - отсортировать исходный файл (так или иначе) и записать его в какой-то результирующий. Так вот, условия задачи это запрещают. Сортировка должна производиться на лету. Напомню, не все, что годится для практической работы, допустимо при выполнении домашки по программированию. ![]() Добавлено ([mergetime]1245604821[/mergetime]): Ёу, 777! -------------------- Я слежу за тобой!
![]() ![]() Цитата Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел. Борис "Бонус" Репетур, "От винта!", выпуск 38. |
|
|
![]()
Сообщение
#130
|
|
![]() Immortal Сообщений: 397 Спасибо сказали: 20 раз ![]() |
Цитата(DracoLich @ 16 Jun 2009, 14:47) Нужно сортировать список из файла, не изменяя в конечном итоге файл. Число записей в файле неограниченно (теоретически), поэтому заносить в массив не получается. Подскажите, как можно реализовать сортировку налету. Язык С++ а в условии нет доп пунка типа и памяти даже на хранение поинтеров на записи не хватает? ![]() вот вам тупой и адцки медленный метод но "на лету" хотя я бы сделал так как я описал: (но дня него надо достаточно памяти чтобы хранить номер записи + еще немножко ![]() делаем линейный проход по ВСЕМУ списку найденый минимальный пишем в выходной файл запоминаем его номер делаем второй проход по списку ищем второй по минимуму(как раз используя сверку с найденным минимальным) и пишем в выходной файл запоминаем номер (все опреации при желании можно реализовать чтением с винта чтобы в памяти держать только пару сотен нужных байт типа смешение в байтах от начала записи текущий проверямый байт записи и т.д.) и т.д. на это у нас памяти хватит? ![]() только предупреждаю вы поседеете ![]() не забудьте определить свой супер длинный тип чисел (например 1мег для хранения числа) и арифмитические операции с ними ![]() ведь у нас почти бесконечность записей ![]() -------------------- Браво, сударь, браво!
|
|
|
![]()
Сообщение
#131
|
|
![]() 😸🧡✊✌️ Сообщений: 16 396 Спасибо сказали: 3231 раз ![]() |
Цитата ведь у нас почти бесконечность записей ![]() А поскольку бесконечные объекты неконструктивны, то они представлены в памяти компьютера быть не могут. Следовательно, задача неверно сформулирована и решена быть не может! ![]() Get serious. Да, блин, прогресс не стоит на месте. Если с десяток лет назад эта задача и была актуальна, то сейчас ее имеет смысл ставить разве что для контроллеров лифта, в которых, я где-то читал, нет printf(). ![]() ![]() Да, я понимаю, что при современных объемах оперативки у персоналок формулировка задачи смешна? Либо файл настолько мал, что его без проблем можно прочитать весть в память и в памяти все отсортировать и вывести на экран, либо файл слишком велик, чтобы поместиться в оперативку, и тогда его вывод на экран, даже без сортировки, займет пару лет. В общем, советов мы надавали, осмысленность задачи обсудили, предлагаю — а ну ее нафик! -------------------- Я слежу за тобой!
![]() ![]() Цитата Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел. Борис "Бонус" Репетур, "От винта!", выпуск 38. |
|
|
![]()
Сообщение
#132
|
|
![]() Banished Сообщений: 1 782 Спасибо сказали: 116 раз ![]() |
ну в прицнипе то обсудили все возможное и невозможное. будем пробовать. Спасибо всем.
-------------------- |
|
|
![]()
Сообщение
#133
|
|
good news, everyone! Сообщений: 918 Спасибо сказали: 93 раза ![]() |
Драколич, сдался? ))
Спросил бы что именно подразумевает препод, и тогда уже сделать. -------------------- этъя опять
|
|
|
![]()
Сообщение
#134
|
|
![]() Banished Сообщений: 1 782 Спасибо сказали: 116 раз ![]() |
да епт )
Ок. Текстовый файл сожержит данные в 3-4 стобцах, нужно орагнизовать сортировку по 1/2/3/4 (любому выбранному) стоблцу. База огромна, и массивы (именно массивы) использовать запрещено. Так яснее? -------------------- |
|
|
![]()
Сообщение
#135
|
|
![]() •●Revolucionario●• Сообщений: 2 467 Спасибо сказали: 5936 раз ![]() |
...А, ну тогда все совсем просто: делай через связанные списки, вряд ли ошибешся.
-------------------- life MOV.I #life+1, *life
האם יש זמן לעצור ? |
|
|
![]()
Сообщение
#136
|
|
![]() 😸🧡✊✌️ Сообщений: 16 396 Спасибо сказали: 3231 раз ![]() |
К.О. говорит, что строка символов — тоже, вообще-то, массив.
![]() Так что совсем без них не обойтись. Даже если просто буферизовать файл, массив нужен. Препод — лось! ![]() -------------------- Я слежу за тобой!
![]() ![]() Цитата Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел. Борис "Бонус" Репетур, "От винта!", выпуск 38. |
|
|
![]()
Сообщение
#137
|
|
![]() Banished Сообщений: 1 782 Спасибо сказали: 116 раз ![]() |
Ну, скорее, опять же мой фейл в некорректности сказаного - нельзя использовать массивы для хранения всей базы, т.к. она не влезет в память. А юзать некоторые ограниченные массивы вполне реально. Нельзя занести всю базу в массив
![]() -------------------- |
|
|
![]()
Сообщение
#138
|
|
![]() •●Revolucionario●• Сообщений: 2 467 Спасибо сказали: 5936 раз ![]() |
Хм, а если занести в массив только данные из использумого для сортировки таблицы столба в комплекте с адресом начала содержащей их строки ?
-------------------- life MOV.I #life+1, *life
האם יש זמן לעצור ? |
|
|
![]()
Сообщение
#139
|
|
![]() thick as a brick Сообщений: 898 Спасибо сказали: 23 раза ![]() |
Вот я оп чем и писал, все умных строят, а чуваку скорее всего что-то до нельзя простое надо, тупо список статики по 3-4 инта.
Добавлено ([mergetime]1245848966[/mergetime]): Нарыл чо то похожее в загашниках, только тут какие-то левые методы есть. И тут одинаковые строки не добавляются, и добавляй элементы сразу в нужное место списка пробегая его от начала, типа пузырёк ![]() Можешь конечно сначала надобавлять, а потом сортировать другим методом. Код #include <stdio.h> #include <stdlib.h> #include <string.h> #include <getopt.h> #define MAX_WORD 64 struct lnode { char *word; struct lnode *next; }; struct lnode *lalloc() { return malloc(sizeof(struct lnode)); } struct lnode *addlist(struct lnode *root, char *w) { struct lnode *p = root; if (p==NULL) { p = lalloc(); p->next = NULL; p->word = (char *) strdup(w); return p; } while (p->next != NULL) { if (strcmp(p->word, w) == 0) return root; else p = p->next; } if (strcmp(p->word, w) == 0) return root; p->next = lalloc(); p = p->next; p->word = (char *) strdup(w); p->next = NULL; return root; } struct lnode *lfree(struct lnode *root) { if (root == NULL) return NULL; struct lnode *p, *tmp; p = root; while (p->next != NULL) { tmp = p->next; free(p->word); free(p); p = tmp; } free(p->word); free(p); return NULL; } void lprint(struct lnode *root) { struct lnode *tmp = root; while(tmp != NULL) { printf("%s ", tmp->word); tmp = tmp->next; } printf("\n"); } int listlen(struct lnode *root) { int count = 0; struct lnode *p = root; while(p != NULL) { p = p->next; ++count; } return count; } char **ltoarr(struct lnode *root, int count) { struct lnode *p = root; int i = 0; char **res = malloc(sizeof(char *) * count); for(;i<count;++i) { res[i] = p->word; p = p->next; } return res; } Добавлено ([mergetime]1245849059[/mergetime]): Какая то <фигня> с форматированием. /Chrono Syndrome: у нас не выражаются, считай предупреждением. |
|
|
![]()
Сообщение
#140
|
|
![]() thick as a brick Сообщений: 898 Спасибо сказали: 23 раза ![]() |
Эм, чувак.
>и массивы (именно массивы) использовать запрещено. >она не влезет в память. Ты уж определись, а то ведь метод с файлами придётся пользовать. |
|
|
![]() ![]() |
Текстовая версия | Сейчас: 25 July 2025 - 20:48 |
Copyright by Алексей Крючков
![]() Programming by Degtyarev Dmitry |
|