IPB

Здравствуйте, гость ( Вход | Регистрация )

9 страниц V  « < 5 6 7 8 9 >  
Reply to this topicStart new topic
> Алгоритмы и формулы
tolich
сообщение 21 Jun 2009, 12:44 (Сообщение отредактировал tolich - 21 Jun 2009, 12:46)
Сообщение #121

😸🧡✊✌️
Сообщений: 16 396
Спасибо сказали: 3231 раз




Понял в чем непонятка! laugh.gif
"Данные не помещаются в оперативную память!" - это по-английски "The data don't fit the RAM", а не "The data aren't placed to the RAM"
То есть, по-русски, оперативки не хватает. laugh.gif

А кешировать лучше сразу две строки (чтобы иметь возможность их сравнивать, как-то так), так что как минимум два буфера. wink.gif


--------------------
Я слежу за тобой!
* tolic.narod.ru

Цитата
Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел.
Борис "Бонус" Репетур, "От винта!", выпуск 38.
Go to the top of the pageAdd Nick
 
+Quote Post
Guevara-chan
сообщение 21 Jun 2009, 13:35 (Сообщение отредактировал Chrono Syndrome - 21 Jun 2009, 13:46)
Сообщение #122

•●Revolucionario●•
Сообщений: 2 467
Спасибо сказали: 5936 раз




Ну, для одиночного сравнения каждой записи хватит и единственного буфера с эталонной строкой, а массовое слабо применимо, если даже (цитирую) "одна запись потенциально тоже не помещается" .


--------------------
life MOV.I #life+1, *life
האם יש זמן לעצור ?
Go to the top of the pageAdd Nick
 
+Quote Post
tolich
сообщение 21 Jun 2009, 16:35
Сообщение #123

😸🧡✊✌️
Сообщений: 16 396
Спасибо сказали: 3231 раз




Сравниваем одну запись с другой, обе в память целиком быть загружены потенциально не могут, обе могут находиться в разных секторах файла. Разумеется, обе записи надо частично загрузить в память, сравнить их начала, если начала совпадают, продолжить загрузку и сравнение, пока не будет найдено первое отличие. Такие дела. Да, еще вначале надо как-то позиционироваться на начало записи.

Вначале нужно вывести минимальную строку, затем вторую по величине, затем третью и т.д. до максимальной. Причем это нужно сделать, не создавая дополнительных файлов и не изменяя исходный.

И еще одна мысль: файл можно открыть два раза (получить два хендла), тогда можно немного упростить работу с текущей позицией.


--------------------
Я слежу за тобой!
* tolic.narod.ru

Цитата
Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел.
Борис "Бонус" Репетур, "От винта!", выпуск 38.
Go to the top of the pageAdd Nick
 
+Quote Post
Guevara-chan
сообщение 21 Jun 2009, 19:01 (Сообщение отредактировал Chrono Syndrome - 21 Jun 2009, 19:05)
Сообщение #124

•●Revolucionario●•
Сообщений: 2 467
Спасибо сказали: 5936 раз




Цитата
Разумеется, обе записи надо частично загрузить в память, сравнить их начала, если начала совпадают, продолжить загрузку и сравнение, пока не будет найдено первое отличие.

Именно, но статические буферы для хранения этих фрагментов не требуются - их вполне можно подержать на стеке, все равно ведь содержимое будет постоянно разрушаться при дозагрузке.

Цитата
Причем это нужно сделать, не создавая дополнительных файлов и не изменяя исходный.

А где сказано, что нельзя использовать дополнительные файлы ?


--------------------
life MOV.I #life+1, *life
האם יש זמן לעצור ?
Go to the top of the pageAdd Nick
 
+Quote Post
tolich
сообщение 21 Jun 2009, 19:17
Сообщение #125

😸🧡✊✌️
Сообщений: 16 396
Спасибо сказали: 3231 раз




Ну, с дополнительным файлом получается вообще легко: создать индексный файл, с записями фиксированного размера, включающими: номер записи исходного файла и смещение от начала файла до начала записи, а затем отсортировать его по возрастанию содержимого записей.
После этого, последовательно проходя по индексу, обработать все записи. (Все нормальные СУБД так делают! laugh.gif)


--------------------
Я слежу за тобой!
* tolic.narod.ru

Цитата
Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел.
Борис "Бонус" Репетур, "От винта!", выпуск 38.
Go to the top of the pageAdd Nick
 
+Quote Post
nLc
сообщение 21 Jun 2009, 19:31 (Сообщение отредактировал Chrono Syndrome - 21 Jun 2009, 19:36)
Сообщение #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
но чем проще алг тем меньше в нем ошибок gigi.gif

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
главное чтобы школота не забыла что все куски надо сортировать одним и тем же методом по которому нам нужен отсортированный итог smile.gif

21.06.2009 19:17:33, I am
минус тока один
на временные файлики нам нужна ТЕМП папка в размере исходного файла

21.06.2009 19:17:44, Chrono Syndrome
Разумеется.

21.06.2009 19:18:12, I am
ну и при диком желании уж операции чтения из кусков мона кешировать блоками по Н кб чтобы винт не убивать gigi.gif

21.06.2009 19:18:56, I am
передавай школоте привед smile.gif

21.06.2009 19:19:08, Chrono Syndrome
smile.gif.

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
Скопипасть).


--------------------
Браво, сударь, браво!
Go to the top of the pageAdd Nick
 
+Quote Post
tolich
сообщение 21 Jun 2009, 20:03
Сообщение #127

😸🧡✊✌️
Сообщений: 16 396
Спасибо сказали: 3231 раз




Идея супер! Признавайтесь, проверка четности целого числа поиском по двум базам данных тоже принадлежит вам?


--------------------
Я слежу за тобой!
* tolic.narod.ru

Цитата
Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел.
Борис "Бонус" Репетур, "От винта!", выпуск 38.
Go to the top of the pageAdd Nick
 
+Quote Post
nLc
сообщение 21 Jun 2009, 20:09
Сообщение #128

Immortal
Сообщений: 397
Спасибо сказали: 20 раз




Цитата(tolich @ 21 Jun 2009, 20:03)
Идея супер! Признавайтесь, проверка четности целого числа поиском по двум базам данных тоже принадлежит вам?

создание подобных предрасчитанных таблиц вполне имеет смысл
например помнитсься в 2000 винде хеш пароля не привязан к аппаратной части а только к паролю
потому однажды созданная реверсная база размером кажется на 8 гигабайт давала в течение пару минут пасс от хеша.
spiteful.gif
и да работа с винтом вполне нормальное явление не надо его стеснятся тем более когда память ограниченна
90% выших хитрых вариантов будут медленней чем обычное решение "в лоб"


--------------------
Браво, сударь, браво!
Go to the top of the pageAdd Nick
 
+Quote Post
tolich
сообщение 21 Jun 2009, 20:20
Сообщение #129

😸🧡✊✌️
Сообщений: 16 396
Спасибо сказали: 3231 раз




Напомню задачу:
Цитата(DracoLich @ 16 Jun 2009, 14:47)
Нужно сортировать список из файла, не изменяя в конечном итоге файл. Число записей в файле неограниченно (теоретически), поэтому заносить в массив не получается. Подскажите, как можно реализовать сортировку налету. Язык С++


То что вы предлагаете - отсортировать исходный файл (так или иначе) и записать его в какой-то результирующий. Так вот, условия задачи это запрещают. Сортировка должна производиться на лету.

Напомню, не все, что годится для практической работы, допустимо при выполнении домашки по программированию. wink.gif

Добавлено ([mergetime]1245604821[/mergetime]):
Ёу, 777!


--------------------
Я слежу за тобой!
* tolic.narod.ru

Цитата
Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел.
Борис "Бонус" Репетур, "От винта!", выпуск 38.
Go to the top of the pageAdd Nick
 
+Quote Post
nLc
сообщение 21 Jun 2009, 21:26 (Сообщение отредактировал nLc - 21 Jun 2009, 21:29)
Сообщение #130

Immortal
Сообщений: 397
Спасибо сказали: 20 раз




Цитата(DracoLich @ 16 Jun 2009, 14:47)
Нужно сортировать список из файла, не изменяя в конечном итоге файл. Число записей в файле неограниченно (теоретически), поэтому заносить в массив не получается. Подскажите, как можно реализовать сортировку налету. Язык С++

а в условии нет доп пунка типа и памяти даже на хранение поинтеров на записи не хватает? spiteful.gif
вот вам тупой и адцки медленный метод но "на лету" хотя я бы сделал так как я описал:
(но дня него надо достаточно памяти чтобы хранить номер записи + еще немножко spiteful.gif )
делаем линейный проход по ВСЕМУ списку
найденый минимальный пишем в выходной файл
запоминаем его номер
делаем второй проход по списку
ищем второй по минимуму(как раз используя сверку с найденным минимальным) и пишем в выходной файл
запоминаем номер
(все опреации при желании можно реализовать чтением с винта чтобы в памяти держать только пару сотен нужных байт
типа смешение в байтах от начала записи
текущий проверямый байт записи и т.д.)
и т.д.
на это у нас памяти хватит? rolleyes.gif
только предупреждаю вы поседеете spiteful.gif
не забудьте определить свой супер длинный тип чисел (например 1мег для хранения числа) и арифмитические операции с ними spiteful.gif
ведь у нас почти бесконечность записей laugh.gif


--------------------
Браво, сударь, браво!
Go to the top of the pageAdd Nick
 
+Quote Post
tolich
сообщение 22 Jun 2009, 00:12
Сообщение #131

😸🧡✊✌️
Сообщений: 16 396
Спасибо сказали: 3231 раз




Цитата
ведь у нас почти бесконечность записей
laugh.gif
А поскольку бесконечные объекты неконструктивны, то они представлены в памяти компьютера быть не могут. Следовательно, задача неверно сформулирована и решена быть не может! laugh.gif

Get serious. Да, блин, прогресс не стоит на месте. Если с десяток лет назад эта задача и была актуальна, то сейчас ее имеет смысл ставить разве что для контроллеров лифта, в которых, я где-то читал, нет printf(). biggrin.gif Да и то — вполне возможно, что и контроллеры лифта давно уже с ним! laugh.gif

Да, я понимаю, что при современных объемах оперативки у персоналок формулировка задачи смешна? Либо файл настолько мал, что его без проблем можно прочитать весть в память и в памяти все отсортировать и вывести на экран, либо файл слишком велик, чтобы поместиться в оперативку, и тогда его вывод на экран, даже без сортировки, займет пару лет.

В общем, советов мы надавали, осмысленность задачи обсудили, предлагаю — а ну ее нафик!


--------------------
Я слежу за тобой!
* tolic.narod.ru

Цитата
Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел.
Борис "Бонус" Репетур, "От винта!", выпуск 38.
Go to the top of the pageAdd Nick
 
+Quote Post
DracoLich
сообщение 22 Jun 2009, 05:49
Сообщение #132

Banished
Сообщений: 1 782
Спасибо сказали: 116 раз




ну в прицнипе то обсудили все возможное и невозможное. будем пробовать. Спасибо всем.


--------------------
Go to the top of the pageAdd Nick
 
+Quote Post
Монца
сообщение 23 Jun 2009, 19:08
Сообщение #133

good news, everyone!
Сообщений: 918
Спасибо сказали: 93 раза




Драколич, сдался? ))
Спросил бы что именно подразумевает препод, и тогда уже сделать.


--------------------
этъя опять
Go to the top of the pageAdd Nick
 
+Quote Post
DracoLich
сообщение 24 Jun 2009, 03:13
Сообщение #134

Banished
Сообщений: 1 782
Спасибо сказали: 116 раз




да епт )
Ок. Текстовый файл сожержит данные в 3-4 стобцах, нужно орагнизовать сортировку по 1/2/3/4 (любому выбранному) стоблцу. База огромна, и массивы (именно массивы) использовать запрещено. Так яснее?


--------------------
Go to the top of the pageAdd Nick
 
+Quote Post
Guevara-chan
сообщение 24 Jun 2009, 09:09 (Сообщение отредактировал Chrono Syndrome - 24 Jun 2009, 09:16)
Сообщение #135

•●Revolucionario●•
Сообщений: 2 467
Спасибо сказали: 5936 раз




...А, ну тогда все совсем просто: делай через связанные списки, вряд ли ошибешся.


--------------------
life MOV.I #life+1, *life
האם יש זמן לעצור ?
Go to the top of the pageAdd Nick
 
+Quote Post
tolich
сообщение 24 Jun 2009, 10:47
Сообщение #136

😸🧡✊✌️
Сообщений: 16 396
Спасибо сказали: 3231 раз




К.О. говорит, что строка символов — тоже, вообще-то, массив. biggrin.gif
Так что совсем без них не обойтись. Даже если просто буферизовать файл, массив нужен. Препод — лось! laugh.gif


--------------------
Я слежу за тобой!
* tolic.narod.ru

Цитата
Всегда приятно осознавать, что кто-то делает что-то хуже, чем делал бы ты, если бы умел.
Борис "Бонус" Репетур, "От винта!", выпуск 38.
Go to the top of the pageAdd Nick
 
+Quote Post
DracoLich
сообщение 24 Jun 2009, 14:37
Сообщение #137

Banished
Сообщений: 1 782
Спасибо сказали: 116 раз




Ну, скорее, опять же мой фейл в некорректности сказаного - нельзя использовать массивы для хранения всей базы, т.к. она не влезет в память. А юзать некоторые ограниченные массивы вполне реально. Нельзя занести всю базу в массив sad.gif


--------------------
Go to the top of the pageAdd Nick
 
+Quote Post
Guevara-chan
сообщение 24 Jun 2009, 15:14
Сообщение #138

•●Revolucionario●•
Сообщений: 2 467
Спасибо сказали: 5936 раз




Хм, а если занести в массив только данные из использумого для сортировки таблицы столба в комплекте с адресом начала содержащей их строки ?


--------------------
life MOV.I #life+1, *life
האם יש זמן לעצור ?
Go to the top of the pageAdd Nick
 
+Quote Post
Gloin
сообщение 24 Jun 2009, 16:10 (Сообщение отредактировал Chrono Syndrome - 24 Jun 2009, 17:22)
Сообщение #139

thick as a brick
Сообщений: 898
Спасибо сказали: 23 раза




Вот я оп чем и писал, все умных строят, а чуваку скорее всего что-то до нельзя простое надо, тупо список статики по 3-4 инта.

Добавлено ([mergetime]1245848966[/mergetime]):
Нарыл чо то похожее в загашниках, только тут какие-то левые методы есть.
И тут одинаковые строки не добавляются, и добавляй элементы сразу в нужное место списка пробегая его от начала, типа пузырёк smile.gif
Можешь конечно сначала надобавлять, а потом сортировать другим методом.

Код
#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: у нас не выражаются, считай предупреждением.
Go to the top of the pageAdd Nick
 
+Quote Post
Gloin
сообщение 24 Jun 2009, 17:25
Сообщение #140

thick as a brick
Сообщений: 898
Спасибо сказали: 23 раза




Эм, чувак.
>и массивы (именно массивы) использовать запрещено.

>она не влезет в память.

Ты уж определись, а то ведь метод с файлами придётся пользовать.
Go to the top of the pageAdd Nick
 
+Quote Post

9 страниц V  « < 5 6 7 8 9 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



Текстовая версия Сейчас: 25 July 2025 - 20:48
Copyright by Алексей Крючков
Strategy Gamez by GrayMage
Programming by Degtyarev Dmitry
  Яндекс.Метрика