Това е всичко за структурата на данните.
Трябва да прочетете входния поток, да прочетете датата, да намерите старите суми за този месец и да добавите новия брой долари и дни обратно към общата сума. (Където казвам "месец", имам предвид месец+година за яснота).
Прост масив по месеци би работил, но тъй като броят на месеците е променлив, това ще изисква програмата да прочете входа два пъти, за да види обхвата на масива, или да ги задържи всичките в паметта, като и двете са потенциално невъзможни. И е лоша структура по други причини.
Следващата стъпка е свързаният списък, съдържащ структура от данни, която включва месеца и общите суми като стойности. Но това ще изисква от вас да откриете дали месецът вече се появява в списъка, което е O(n) за всеки ред на въвеждане.
Още една стъпка нагоре. Съхранявайте месеца/сумата в двоично дърво, сортирано (индексирано) по месец - "сортиран списък". За намиране на подходящия месец е дневникът на поръчките (месеци във входния поток), който не може да бъде твърде голям, тъй като дори 10 години са само 120 месеца. Това има предимството, че няма да се налага да сортирате отново данните за изходния отчет и вероятно е това, което те искат да използвате.
Вероятно най-ефективната структура е това, което понякога се нарича "Речник". Прекалено, освен ако нямате хиляди месеци. http://www.dotnetperls.com/dictionary обяснява тази структура на данните. Други среди имат подобни неща; това е вариант на стандартна хеш таблица. Различните класове на речника имат помощни функции, за да ви кажат броя на стойностите, да изброят ключовете, да ви кажат дали вече съществува ключ и т.н. - нещо, от което се нуждаете. Бихте използвали месец/година като ключ и брой долари и брой клиенти като съхранени стойности. Речниците са с постоянно време, така че са ефективни (но подозирам, че прекаляват).
person
Peter Webb
schedule
02.06.2013
