В задачата от последното домашно - голямо сортиране, не се казва къде трябва да се извежда резултата - дали на стандартния изход или да се презапише файла. Не се казва даже дали трябва да се извежда резултат, нито пък - в какъв формат (текстов/двоичен/космичен....).
Трябва ли да се съобразяваме с големината буферите, които се използват от стандартните функции за вход/изход (т.е да използваме функции без буфериране при достатъчно малко N)?
Има ли някаква долна граница за N? В смисъл ако N е 1 трябва число по число да извличаме от входния файл (до тук добре) и после да пишем във някакъв външен файл по 4 байта .... което ми се вижда супер бавно (даже да не гледаме самото сортиране).
Защо входния файл който сте дали е сортиран? Направо да го обърнем наопъки :) А да - задачата я няма в споджо (ако беше там въобще нямаше да пиша тук).
В условито се казва "... максималния брой числа от файла, които програмата има право да пази едновременно в паметта." Това означава ли че може да пазим числа, които не са от файла (примерно някакви индекси) които са много на брой в паметта?
Файлът трябва да се сортира, т.е. файлът трябва да се презаписва в същият формат.
Не трябва да се съобразявате с големината на буферите, ако искаш формална дефиниция приеми, че можеш да ползваш 4 * N байта (за масив от N цели числа) + 1 KB (за някакви локални променливи). Приеми, че N е поне 100.
Дадения тест е примерен, ако искаш предай програма, която обръща файла наопъки, но не мисля, че това отговаря на условието на задачата :).
Задачата няма да я има в spoj0, решението се оценява от асистент, т.е. ако използваш 2 KB или дори 4 * N байта повече, не е фатално.
Не трябва да се съобразявате с големината на буферите, ако искаш формална дефиниция приеми, че можеш да ползваш 4 * N байта (за масив от N цели числа) + 1 KB (за някакви локални променливи). Приеми, че N е поне 100.
Дадения тест е примерен, ако искаш предай програма, която обръща файла наопъки, но не мисля, че това отговаря на условието на задачата :).
Задачата няма да я има в spoj0, решението се оценява от асистент, т.е. ако използваш 2 KB или дори 4 * N байта повече, не е фатално.
Абе, аз ли съм единственият, на когото му се струва странно, че теглим и разархивираме(макар и само) 4.7 МБ архив, вместо следната програма:
#include<stdio.h>
int main()
{
FILE * f = fopen("input.txt","wt");
int x;
int MAX = 50000000;
for(x=1;x<=MAX;x++)
{
fprintf(f,"%d ", x);
}
fprintf(f,"\n");
fclose(f);
return 0;
}
:)
#include<stdio.h>
int main()
{
FILE * f = fopen("input.txt","wt");
int x;
int MAX = 50000000;
for(x=1;x<=MAX;x++)
{
fprintf(f,"%d ", x);
}
fprintf(f,"\n");
fclose(f);
return 0;
}
:)
Това може би е проява на обсесивно-компулсивно разстройство, но имам един въпрос.
Искам да си създам временни файлове за програмата(очевидно ще ми трябват). Искам това да става във временна папка.
Искам да имам 100% сигурност, че тази папка не съществува в момента на стартиране на програмата.
Как да избера име?
Искам да си създам временни файлове за програмата(очевидно ще ми трябват). Искам това да става във временна папка.
Искам да имам 100% сигурност, че тази папка не съществува в момента на стартиране на програмата.
Как да избера име?
#include <stdio.h>
char *tmpnam(char *)
От друга страна не съм съвсем сигурен за portable функция, която създава директории (има mkdir във <sys/stat.h> / <sys/types.h> обаче пише че конформва posix/bsd ... което не знам какво значи за windows).
Със сигурност system("mkdir XXXX"); ще работи и на 2те: http://cplusplus.com/forum/general/4575/
char *tmpnam(char *)
От друга страна не съм съвсем сигурен за portable функция, която създава директории (има mkdir във <sys/stat.h> / <sys/types.h> обаче пише че конформва posix/bsd ... което не знам какво значи за windows).
Със сигурност system("mkdir XXXX"); ще работи и на 2те: http://cplusplus.com/forum/general/4575/
Мм, проблемче.
Има някаква скрита функционалност, която не схващам.
това работи:
char name[2];
name[0] = 'a';
name[1] = 0;
name[0] += b;
save_n_numbers(name, N, arr);
това - не:
char name[L_tmpnam + 1];
save_n_numbers(tmpnam(name), N, arr);
Не създава файлове както трябва.
Вътре във функцията се създават с:
FILE * f = fopen(filename, "wt");
Естествено, мога да си го направя и с мой си генератор. Просто се чудя защо готовият не работи.
Има някаква скрита функционалност, която не схващам.
това работи:
char name[2];
name[0] = 'a';
name[1] = 0;
name[0] += b;
save_n_numbers(name, N, arr);
това - не:
char name[L_tmpnam + 1];
save_n_numbers(tmpnam(name), N, arr);
Не създава файлове както трябва.
Вътре във функцията се създават с:
FILE * f = fopen(filename, "wt");
Естествено, мога да си го направя и с мой си генератор. Просто се чудя защо готовият не работи.
В условието е казано, че програмата ни би трябвало да работи към 10 минути за този вход. Това при какво N е, защото (поне аз така си мисля) performance-ът на реализацията ще зависи пряко от временната памет?
Прав си, че ще зависи. Обаче, също така от значение е колко бързо става създаването и триенето на файлове на твоята система.
Ето ти малко практически резултати.
Програмата ми ползва еднакво количество(като байтове) външна памет и в двата случая:
# 16 MB RAM
$ time ./big_sort input.txt 4000000
real 0m40.583s
user 0m36.042s
sys 0m3.544s
# 160 B RAM
$ time ./big_sort input.txt 40
real 4m6.855s
user 1m59.723s
sys 1m58.427s
Това, естествено, трябва да бъде прието по-скоро като фукане колко ми е хубав компютърът, отколкото колко оптимизирана ми е програмата.
real е времето от пускането на командата, до изкарването на резултат.
user е времето, през което моята програма е сортирала
sys е времето, през което операционната система е създавала и триела файлове.
real != user + sys, но защо е така трябва да питате Линус Торвалдс.
Работата е там, че когато N е малко, половината изхабено време всъщност не е прекарано в моята програма!
Мога да си скъсам задника да оптимизирам, тези 1.58 минути няма да намалеят по никакъв начин.
Това съм го тествал на Линукс. Нямам представа дали на Уиндоус ще бъде подобна скоростта.
Но със сигурност има долна граница за колко най-малко време може да свърши програмата, и тя не зависи от самата програма.
Ето ти малко практически резултати.
Програмата ми ползва еднакво количество(като байтове) външна памет и в двата случая:
# 16 MB RAM
$ time ./big_sort input.txt 4000000
real 0m40.583s
user 0m36.042s
sys 0m3.544s
# 160 B RAM
$ time ./big_sort input.txt 40
real 4m6.855s
user 1m59.723s
sys 1m58.427s
Това, естествено, трябва да бъде прието по-скоро като фукане колко ми е хубав компютърът, отколкото колко оптимизирана ми е програмата.
real е времето от пускането на командата, до изкарването на резултат.
user е времето, през което моята програма е сортирала
sys е времето, през което операционната система е създавала и триела файлове.
real != user + sys, но защо е така трябва да питате Линус Торвалдс.
Работата е там, че когато N е малко, половината изхабено време всъщност не е прекарано в моята програма!
Мога да си скъсам задника да оптимизирам, тези 1.58 минути няма да намалеят по никакъв начин.
Това съм го тествал на Линукс. Нямам представа дали на Уиндоус ще бъде подобна скоростта.
Но със сигурност има долна граница за колко най-малко време може да свърши програмата, и тя не зависи от самата програма.
Да силно зависи от N, също така зависи и от компютъра. Има се предвид N = O(10 000) примерно.