Neri-kun Ответов: 3

Можно ли вставить новую строку в сортированный массив строк, используя алгоритм двоичного поиска?

У меня есть файл,который содержит список слов,которые расположены в алфавитном порядке.Сначала,когда я хотел вставить новое слово в файл,я просто зацикливался на строках файла в линейном времени.Затем я подумал:"поскольку все строки всегда упорядочены в алфавитном порядке,не могу ли я найти наилучшее положение для новой строки за логарифмическое время?".


P. S:Я знаю,что имя функции не имеет никакого отношения, поэтому, пожалуйста, не возражайте и извините за некоторые комментарии на моем родном языке.

Что я уже пробовал:

void insertion_sort(FILE** file_ptr,char* new_word) {

	int no_current_word = 0;
	int saved_position;
	char* current_word[SIZE];
	char current_line[SIZE];
	char* new_buffer=(char*)malloc(BUFFER_MAX_SIZE);
	*file_ptr = fopen("Lista cuvinte.txt", "r+");
	while (fgets(current_line, BUFFER_MAX_SIZE, *file_ptr)) {
		current_word[no_current_word] = (char*)malloc(strlen(current_line)+1);
		strcpy(current_word[no_current_word], current_line);
		no_current_word++;
	}
	for (int i = 0; i < no_current_word; i++) {
		if (strcmp(current_word[i], new_word) > 0) {
			saved_position = i;
			break;
		}
	}
	current_word[no_current_word++] = (char*)malloc(10); //la un moment dat clar o sa fac update la aceasta abordare!
	if (strcmp(new_word, current_word[no_current_word - 2]) > 0)
		strcpy(current_word[no_current_word-1], new_word);
	else {
		for (int i = no_current_word - 1; i > saved_position; i--)
			strcpy(current_word[i], current_word[i - 1]);
		strcpy(current_word[saved_position], new_word);
	}
	strcpy(new_buffer, current_word[0]);
	for (int i = 1; i < no_current_word; i++)
		strcat(new_buffer, current_word[i]);
	*file_ptr = fopen("Lista cuvinte.txt", "w");	//va trebui sa resterg continutul atunci cand il voi re-updata
	fprintf(*file_ptr, "%s", new_buffer);
	rewind(*file_ptr);
	printf("%s", new_buffer);
	printf("\n\n");
}
```

3 Ответов

Рейтинг:
2

OriginalGriff

Я бы сделал это так: создал индексный файл: скажем, 26 записей, дав вам смещение файла к первому слову, начинающемуся с "А", "В", "С"...

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

Рейтинг:
1

k5054

You have to read the whole file anyway, so you can't help doing that. And, unless your words are all exactly the same length, you can't really do a binary search on the file, since you don't know how many bytes to jump forward/back to find the next record of interest. Even when you've found it, you've got to read the rest of the file in, write out the new word, then write out the buffer again. You might as well read the entire file into a buffer, walk sequentially through the buffer until you find where you want to put the new word then write the buffer to where you are now, the new word, and then the rest of the buffer. This is still linear in time, but since you're only doing one read and 2 or 3 writes it should be much faster e.g:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void insert_word(const char *file_name, const char *new_word)
{
    FILE *wlist = fopen(file_name, "r+");

    /* find out how big the file is */
    fseek(wlist, 0, SEEK_END);
    size_t nbytes = ftell(wlist);
    rewind(wlist);

    /* alloc a buffer for file */
    /* we'll be doing string ops, so allow for trailing nul */
    char *buffer = malloc(nbytes+1);

    /* now read the file into the buffer */
    fread(buffer, nbytes, 1, wlist);
    buffer[nbytes] = 0;
    rewind(wlist);

    char *word_begin = buffer;
    char *word_end = strchr(buffer, '\n');
    while( *word_begin ) {
        int cmp = strcoll(word_begin, new_word);
        if(cmp == 0) {
            break; /* word already in file */
        } else if( cmp > 0 ) {
            /* found location to put word */
            /* write the buffer up to this point */
            size_t buffer_to_here = word_begin - buffer;
            fwrite(buffer, buffer_to_here, 1, wlist);

            /* add the new word */
            fprintf(wlist, "%s\n", new_word);

            /* write the rest of the buffer */
            size_t buffer_to_end = nbytes - buffer_to_here;
            fwrite(word_begin, buffer_to_end, 1, wlist);
            break;
        }
        /* if we get here, move to the next word */
        word_begin = word_end + 1; /* after the \n pointed to by word_end */
        word_end = strchr(word_begin, '\n');
    }

    /* got to the end of the file, so word is appended */
    if(*word_begin == '\0') {
        fseek(wlist, 0, SEEK_END);
        fprintf(wlist, "%s\n", new_word);
    }

    /* clean up */
    fclose(wlist);
    free(buffer);
}


Я опустил проверку ошибок в приведенном выше, чтобы уменьшить беспорядок. Там действительно должны быть проверки после malloc, fopen, fread, fwrite. Я использую strcoll (), а не strcmp (), так как порядок слов может быть значительным через локаль. Не забудь позвонить locale(LC_COLLATE, "") прежде чем позвонить сюда. Сравнение завершится в худшем случае на длине new_word, независимо от длины от word_begin до конца буфера, поэтому нет никаких опасений, что вы можете сравнивать мегабайты данных. Я протестировал это на RPI2 и смог добавить "zzzzzzzzz" в конец списка примерно из 500 000 слов в файле размером 4,8 МБ примерно за 250 мс.

Обратите внимание, что ваше решение не вызывает free() для всего, что вы malloc(). Не делать этого означает, что у вас будет утечка памяти, и если вы находитесь в системе с ограниченной памятью, вы можете запустить ее при повторном вызове. В моем решении я передаю имя файла для работы над ним. Если вы хотите использовать уже открытый указатель файла, вам просто нужно передать его как FILE * В этом случае у вас есть требование, чтобы вызывающий абонент открыл файл с режимом "r+".

Обновление:
на самом деле, мы можем сохранить запись здесь:
/* found location to put word */
/* write the buffer up to this point */
size_t buffer_to_here = word_begin - buffer;
fwrite(buffer, buffer_to_here, 1, wlist);

Мы не изменили файл, поэтому вместо этого мы можем просто fseek() : 
fseek(wlist, buffer_to_here, SEEK_SET);
Это небольшое улучшение, но оно экономит некоторые дисковый ввод-вывод.

Рейтинг:
0

Patrice T

Цитата:
Можно ли вставить новую строку в сортированный массив строк, используя алгоритм двоичного поиска?

Это зависит.
Чтобы сделать то, что вы хотите, вам нужно знать, где находится N-е слово в файле, проблема в том, что слова имеют переменную длину.
Таким образом, с плоским текстовым файлом переменной длины практично только последовательное чтение/запись.
"a"
"abc"
"ac"
"b"

Альтернативой является заполнение каждого слова пробелами до определенной длины, так что N-я позиция слова равна n * длине строки. В данном случае это работает.
"a   "
"abc "
"ac  "
"b   "

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