В файл записываются последовательности с клавиатуры

Question

В файл записываются последовательности с клавиатуры

Рейтинг: 0Ответов: 1Опубликовано: 25.01.2023

Не нужен код, нужна светлая идея!!!Вся проблема задачи в эффективном использовании памяти...

Последовательности задаются любой длины.
Последовательности при вводе отделяются друг от друга специальным символом например: (1 2 4 * 5 94 7).
Последовательности записываются в файл, если накопилось 10 чисел - последовательность продолжает записываться на новой строке.
Встретился разделитель - конец последовательности, тоже новая строка.

Самая загвоздка

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

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

c# память

Источник: Stack Overflow на русском

Answer 1

▲ 2

Светлая идея состоит в том чтобы попробовать какую-то реализацию. Если она подходит по производительности, идти дальше решать задачу, не рассуждая "о способах заточки мечей".

Миллион целых чисел генерируется и считывается за одну десятую секунды. Девять десятых времени уходит на работу scanf:

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


typedef struct {
    size_t size;
    size_t capacity;
    int *data;
} array_t;


void reserve(array_t *array, size_t capacity) {
    if (capacity > array->capacity) {
        int *data = realloc(array->data, capacity * sizeof(array->data[0]));
        if (data == NULL) {
            fprintf(stderr, "memory error\n");
            exit(1);
        }
        array->capacity = capacity;
        array->data = data;
    }
}

void append(array_t *array, int n) {
    if (array->size == array->capacity) {
        reserve(array, (array->capacity == 0) + 2 * array->capacity);
    }
    array->data[array->size] = n;
    ++array->size;
}

int main() {
    array_t array = {0};
    int n;
    while(scanf("%d", &n) == 1) {
        append(&array, n);
    }
    printf("%zu ints were read", array.size);
}

$ gcc -std=c11 -pedantic -Wall -Wextra -Werror -Wwrite-strings -Wconversion read.c 

$ time seq 1000000 | ./a.out
1000000 ints were read
real  0m0.099s
user  0m0.108s
sys   0m0.000s

Если поменять main можно измерить накладные расходы заполнение массива неизвестной длины. Одна сотая секунды. При том что выключены любые оптимизации:

int main() {
    array_t array = {0};
    for (int n = 0; n < 1000000; ++n) {
        append(&array, n);
    }
    printf("%zu ints were appended", array.size);
}

$ gcc -std=c11 -pedantic -Wall -Wextra -Werror -Wwrite-strings -Wconversion append.c 

$ time ./a.out
1000000 ints were appended
real  0m0.008s
user  0m0.004s
sys   0m0.000s

В файл записываются последовательности с клавиатуры

Ответы