Heisann
Jeg har et kinkig problem i to dimensjoner. Jeg har klart å dele det opp i et delproblem i en dimensjon som (forhåpentligvis) vil hjelpe meg å løse hovedproblemet. Dette mindre problemet er dessuten interessant også på generell basis. Så jeg spør her etter løsningsforslag og diskusjon om delproblemet. Det jeg skal implementere er en abstrakt datatype som jeg skal beskrive her:
ADT Table
Get(y): Return pointer to element y if y exists in the table
Create(y): Return pointer to element y. If y doesn't exist, create it.
Delete(y): Delete element y from the table.
InsertRows(beforeY, count): Insert a number of rows, or empty elements, before element y
Presiseringer:
1. Elementer aksesseres by position (y). Noe som impliserer at hvis man setter inn to rader/elementer mellom element 2 og 3 vil det som før var element 5 nå bli element 7.
2. Det vil være store mengder elementer som ikke er laget og (flesteparten av) disse skal ikke lagres i strukturen ("sparse data structure").
Ytelse:
3. Get(), Create() skal skalere godt.
4. InsertRows() skal skalere godt.
5. (Bonus hvis Delete() også er rimelig skalerbar.)
De fleste punktene er helt greie krav hver for seg. Man kan løse punkt 1 og 2 med en linked list. Men dette ødelegger ytelsen til Get(). Man kan få en god ytelse på Get() ved å bruke en trestruktur eller hashtable med y som nøkkel. Men bruken av nøkler ødelegger ytelsen til InsertRows(). Kombinasjonen av flere krav samtidig gjør altså dette til et mer utfordrende problem.
Noen ideer eller synspunkter?
Jeg har et kinkig problem i to dimensjoner. Jeg har klart å dele det opp i et delproblem i en dimensjon som (forhåpentligvis) vil hjelpe meg å løse hovedproblemet. Dette mindre problemet er dessuten interessant også på generell basis. Så jeg spør her etter løsningsforslag og diskusjon om delproblemet. Det jeg skal implementere er en abstrakt datatype som jeg skal beskrive her:
ADT Table
Get(y): Return pointer to element y if y exists in the table
Create(y): Return pointer to element y. If y doesn't exist, create it.
Delete(y): Delete element y from the table.
InsertRows(beforeY, count): Insert a number of rows, or empty elements, before element y
Presiseringer:
1. Elementer aksesseres by position (y). Noe som impliserer at hvis man setter inn to rader/elementer mellom element 2 og 3 vil det som før var element 5 nå bli element 7.
2. Det vil være store mengder elementer som ikke er laget og (flesteparten av) disse skal ikke lagres i strukturen ("sparse data structure").
Ytelse:
3. Get(), Create() skal skalere godt.
4. InsertRows() skal skalere godt.
5. (Bonus hvis Delete() også er rimelig skalerbar.)
De fleste punktene er helt greie krav hver for seg. Man kan løse punkt 1 og 2 med en linked list. Men dette ødelegger ytelsen til Get(). Man kan få en god ytelse på Get() ved å bruke en trestruktur eller hashtable med y som nøkkel. Men bruken av nøkler ødelegger ytelsen til InsertRows(). Kombinasjonen av flere krav samtidig gjør altså dette til et mer utfordrende problem.
Noen ideer eller synspunkter?
Sitat av Hovedproblemet
Til slutt tar jeg med hovedproblemet, som dere godt kan hoppe over. Det er en datastruktur med rader og kolonner som ser slik ut:
Get(x, y): Return pointer to element (x, y) if it exists in the table
Create(x, y): Return pointer to element (x, y). If it doesn't exist, create it.
Delete(x, y): Delete element (x, y) from the table.
InsertRows(beforeY, count): Insert a number of rows (with empty elements) before row Y
InsertCols(beforeX, count): Insert a number of columns (with empty elements) before column X
Get(x, y): Return pointer to element (x, y) if it exists in the table
Create(x, y): Return pointer to element (x, y). If it doesn't exist, create it.
Delete(x, y): Delete element (x, y) from the table.
InsertRows(beforeY, count): Insert a number of rows (with empty elements) before row Y
InsertCols(beforeX, count): Insert a number of columns (with empty elements) before column X
Vis hele sitatet...
