|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
09.02.2014, 18:55 | #11 |
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
Самое простое решение, которое приходит в голову:
1) Храним просто массив из пар (номер стека, значение). На каждую такую запись достаточно 40 бит (т. е. 5 байт) - можем сразу выделить 500 килобайт одним куском. 2) На каждый пуш дописываем к массиву новую запись. 3) На каждый поп ищем, начиная с конца массива, первую запись, у которой номер стека совпадает с искомым; выводим ее значение; помечаем запись как пустую. Непонятно, правда, успеет ли такое брутфорсное решение вложиться во временной лимит. Если нет - придется запоминать в отдельном массиве информацию об индексах, в которых лежат вершины стеков. |
09.02.2014, 20:22 | #12 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Можно не скупиться и взять сразу 600 байт..
Но боюсь, не пройдем.. 500к на пуши + 499.999+499.998 + .. + 2 + 1.. = 500к + 500к(500к)/2.. не пройдем.. Вот код.. Он снова падает на 10 тесте из-за той же самой памяти.. Код:
|
09.02.2014, 20:35 | #13 |
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
Подозреваю, что из-за выравнивания сейчас sizeof(a) будет равно 800000 по крайней мере в делфи было бы так.
|
10.02.2014, 06:34 | #14 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Массив структур выравнивает..
Создал 2 массива по 4 и 2 байта каждый.. Всё равно не прохожу по памяти.. Убрал модуль и использовал стандартный Val.. Память - ОК.. время - снова 10 Переписал Val ручками - 11 тест по времени Этот вариант отпадает.. И я кажется понял, почему падает вариант с SetLength().. ведь мы сначала выделим память, а затем копируем, а потом уже освободим.. И тогда в этот момент памяти у нас в 2 раза больше.. вот и нашли пропажу.. (Беру свои слова по поводу SetLength'a обратно..) |
10.02.2014, 16:53 | #15 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Ромаха, используя такое все прошло. 17 бит на индекс-указатель и 30 бит на значение - итого 6 байт, даже один бит лишний
Код:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
10.02.2014, 17:02 | #16 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Супер..
А можно чуть-чуть подробнее? в stacks храним указатели на 1-ый элемент? values хранят значение и указатель на следующий элемент? |
10.02.2014, 17:12 | #17 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Ага. Может лучше код вложением, что бы много букв не было?
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
10.02.2014, 17:13 | #18 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Хотелось бы самому написать.. (можно пару слов об идее, если Вам не в тягость)
|
10.02.2014, 17:19 | #19 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Индексы для values от 1 до 100000 (max 7 бит) - адресуют не каждый байт в массиве, а группу из шести байтов. В первых трех байтах и старших 6 битах 4-го - значение. В последних двух байтах и младшем бите 4-го - индекс на следующий. Те же списки, но чуть хитрей. Данные приходится побайтно засовывать с использованием битовых сдвигов, AND и OR. И читать тоже
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 10.02.2014 в 17:21. |
10.02.2014, 21:32 | #20 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Огромное спасибо!..
Завтра попытаюсь закодить.. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Оптимизация по памяти алгоритма пойска k-той статистики (Язык C) | PathTheir | Помощь студентам | 2 | 02.04.2014 23:48 |
Оптимизация памяти | winhttp | C# (си шарп) | 1 | 09.09.2012 09:54 |
Кольцевая очередь на массиве в статической памяти с элементами в динамической памяти | ]tach[ | Общие вопросы C/C++ | 1 | 19.01.2011 13:16 |
...оптимизация памяти... вопрос.... | maxvip | Операционные системы общие вопросы | 5 | 12.01.2010 15:17 |
Оптимизация использования оперативной памяти | Lkhasa | Общие вопросы Delphi | 4 | 04.07.2008 15:22 |