Programming Perle 1.6.1

Question

Programming Perle 1.6.1

#1 da (3 voti)

1

Ho appena iniziato a programmare Perle e ho già perso la forma rispetto alla prima domanda nella Colonna 1. Il problema è di ordinare un file con un massimo di 10 milioni di elementi a 7 cifre senza vincoli di memoria. La soluzione è la seguente:

int intcomp(int *x, int *y)
{  return *x - *y; }
int a[1000000];
int main(void)
{  int i, n=0;
   while (scanf("%d", &a[n]) != EOF)
     n++;
   qsort(a, n, sizeof(int), intcomp);
   for (i=0; i < n; i++)
     printf("%d\n", a[i]);
   return 0;
 }

Le mie domande sono, perché l'array intero è inizializzato solo per memorizzare un milione e non dieci milioni? Nella soluzione bitmap nella sezione 1.4, utilizziamo una bitmap da 10 milioni di bit. Non entreremo nello spazio di memoria non allocato?

grazie!

c

posta user1367123 13.07.2016 - 07:25

fonte

1 risposta

Leggi altre domande sui tag c

Qual è la differenza tra AUTOSAR e DDS? Challenge design Elevator [chiuso]

score 3 · Answer 1

È importante ricordare che il punto del capitolo (e del libro) era come decostruire il problema per trovare una soluzione ottimizzata per i suoi vincoli, non come ordinare dati arbitrari. In quanto tale, l'esempio che usa qsort è un throwaway.

Tuttavia, è scritto molto male, anche dal punto di vista degli anni '70; Immagino che l'incarico sia stato affidato a uno degli studenti di Bentley. Ecco alcuni dei problemi:

Dimensione errata dell'array. Questo potrebbe essere stato risolto utilizzando una costante. Anche se vedi sotto.
Mix di preoccupazioni: la lettura, l'ordinamento e la scrittura sono tre cose diverse e devono essere gestite da tre diverse funzioni. OK, questo è il dogma del 21 ° secolo, quindi forse Bentley o il suo studente possono essere perdonati. Nasconde ancora il core qsort in molte letture e scritture superflue.
La funzione di confronto non sarà valida per le combinazioni degli interi minimi e massimi. Un confronto corretto deve prestare attenzione al bit di trasporto. Si potrebbe sostenere che il testo applica un vincolo di "interi positivi", ma in tal caso la funzione dovrebbe essere denominata posintc (sto mantenendo fino a 7 caratteri perché ricordo questo come un precoce requisito di linker * nix; un programmatore moderno dovrebbe usare il compare_positive_ints_by_ref molto più lungo ma più descrittivo.
Nessun controllo dei limiti: il lettore legge fino alla fine del file, e se lo dai più di 1.000.000 di voci supereranno felicemente il buffer. Questo è il problema più grande di IMO.

Detto questo, stai anche iniettando i tuoi requisiti. Ecco la dichiarazione del problema, da pagina 7 della 2a edizione, 20esima stampa:

If memory were not scarce, how would you implement a sort in a language with libraries for representing and sorting sets?

È vero, il testo parla di un file più grande. Ma questo non è esplicitamente menzionato nel problema. E i programmatori IMO aggiungendo quello che pensano siano requisiti è un grosso problema con il nostro settore.