Алгоритмы и формулы Опции

[tolich]

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

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

[Guevara-chan]

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

[tolich]

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

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

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

[Guevara-chan]

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

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

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

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

[tolich]

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

[nLc]

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

[tolich]

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

[nLc]

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

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

и да работа с винтом вполне нормальное явление не надо его стеснятся тем более когда память ограниченна
90% выших хитрых вариантов будут медленней чем обычное решение "в лоб"

[tolich]

Напомню задачу:

Нужно сортировать список из файла, не изменяя в конечном итоге файл. Число записей в файле неограниченно (теоретически), поэтому заносить в массив не получается. Подскажите, как можно реализовать сортировку налету. Язык С++

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

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

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

[nLc]

Нужно сортировать список из файла, не изменяя в конечном итоге файл. Число записей в файле неограниченно (теоретически), поэтому заносить в массив не получается. Подскажите, как можно реализовать сортировку налету. Язык С++

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

[tolich]

ведь у нас почти бесконечность записей

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

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

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

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

[DracoLich]

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

[Монца]

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

[DracoLich]

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

[Guevara-chan]

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

[tolich]

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

[DracoLich]

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

[Guevara-chan]

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

[Gloin]

Вот я оп чем и писал, все умных строят, а чуваку скорее всего что-то до нельзя простое надо, тупо список статики по 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: у нас не выражаются, считай предупреждением.

[Gloin]

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

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

Ты уж определись, а то ведь метод с файлами придётся пользовать.