4430
правок
B-деревья без явного задания параметров кэша: различия между версиями
Материал из WEGA
B-деревья без явного задания параметров кэша (посмотреть исходный код)
Версия от 21:23, 8 февраля 2017
, 8 февраля 2017→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
== Применение == | == Применение == | ||
Словари решают фундаментальную проблему структурирования данных, являясь компонентом решений исключительно высокого числа вычислительных задач. Словари для внешней памяти полезны в ситуациях, когда основное время выполнения тратится на обращения к памяти; словари без явного задания параметров кэша выделяются среди других своей способностью оптимизировать доступ ко всем уровням неизвестной иерархии памяти. Это может пригодиться, например, при разработке программ, которые будут работать на различных или неизвестных архитектурах (таких как библиотечные програмы или программы для гетерогенных распределенных вычислений – например, сетевых коллективных вычислений и проектов наподобие SETI@home). Даже на единственной и известной архитектуре параметры памяти, доступные вычислительному процессу, могут быть непостоянными, если несколько процессов конкурируют за одни и те же ресурсы памяти. Поскольку алгоритмы без явного задания параметров кэша оптимизированы для всех значений параметров, они потенциально способны лучше адаптироваться к подобным изменениям, а также к различным размерам входных данных, вынуждающих использовать различные уровни памяти. | |||
== Открытые вопросы == | |||
Для обсуждаемой задачи упорядоченного одномерного словаря один из важных открытых вопросов касается поиска структуры данных, обеспечивающей все перечисленные в теореме 3 границы для худшего случая. | |||
== Экспериментальные результаты == | |||
Словари без явного задания параметров кэша эмпирически рассматривались в работах [11, 13, 16, 20, 22]. В целом считается, что методы без явного задания параметров кэша легко могут превзойти по эффективности RAM-алгоритмы, хотя иногда не в такой степени, как алгоритмы, специально приспособленные для конкретной иерархии памяти и размера задачи. С другой стороны, алгоритмы без явного задания параметров кэша хорошо работают на всех уровнях иерархии памяти, а также более устойчивы к изменению размеров задач. | |||
== См. также == | |||
* [[B-деревья]] | |||
* [[Модель без явного задания параметров кэша]] | |||
* [[Сортировка без явного задания параметров кэша]] | |||
* [[Модель ввода-вывода]] | |||
== Литература == | |||
1. Aggarwal, A., Vitter, J.S.: The Input/Output complexity of sorting and related problems. Commun. ACM 31(9), 1116-1127 (1988) | |||
2. Arge, L., Brodal, G.S., Fagerberg, R.: Cache-oblivious data structures. In: Mehta, D., Sahni, S. (eds.) Handbook on Data Structures and Applications. CRC Press, Boca Raton (2005) | |||
3. Arge, L., Brodal, G.S., Fagerberg, R., Laustsen, M.: Cache-oblivious planar orthogonal range searching and counting. In: Proc. 21st ACM Symposium on Computational Geometry, pp. 160-169. ACM, New York (2005) | |||
4. Arge, L., de Berg, M., Haverkort, H.J.: Cache-oblivious R-trees. In: Proc. 21st ACM Symposium on Computational Geometry, pp. 170-179. ACM, New York (2005) | |||
5. Arge, L., Vitter, J.S.:Optimal external memory interval management. SIAM J. Comput. 32(6), 1488-1508 (2003) | |||
6. Arge, L., Zeh, N.: Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching. In: Proc. 22nd ACM Symposium on Computational Geometry, pp. 158-166. ACM, New York (2006) | |||
7. Bender, M., Cole, R., Demaine, E., Farach-Colton, M.: Scanning and traversing: Maintaining data for traversals in a memory hierarchy. In: Proc. 10th Annual European Symposium on Algorithms. LNCS, vol. 2461, pp. 139-151. Springer, Berlin (2002) | |||
8. Bender, M., Cole, R., Raman, R.: Exponential structures for cache-oblivious algorithms. In: Proc. 29th International Colloquium on Automata, Languages, and Programming. LNCS, vol. 2380, pp. 195-207. Springer, Berlin (2002) | |||
9. Bender, M.A., Brodal, G.S., Fagerberg, R., Ge, D., He, S., Hu, H., Iacono, J., Lopez-Ortiz, A.: The cost of cache-oblivious searching. In: Proc. 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 271-282. IEEE Computer Society Press, Los Alamitos (2003) | |||
10. Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. SIAM J. Comput. 35(2), 341-358 (2005). Conference version appeared at FOCS (2000) | |||
11. Bender, M.A., Duan, Z., Iacono, J., Wu, J.: A locality-preserving cache-oblivious dynamic dictionary. J. Algorithms 53(2), 115-136 (2004). Conference version appeared at SODA (2002) | |||
12. Bender, M.A., Farach-Colton, M., Fineman,J.T., Fogel,Y.R., Kuszmaul, B.C., Nelson, J.: Cache-oblivious streaming B-trees. In: Proc. 19th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 81-92. ACM, New York (2007) | |||
13. Bender, M.A., Farach-Colton, M., Kuszmaul, B.C.: Cache-oblivious string B-trees. In: Proc. 25th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 233-242. ACM, New York (2006) | |||
14. Bender, M.A., Fineman, J.T., Gilbert, S., Kuszmaul, B.C.: Concurrent cache-oblivious B-trees. In: Proc. 17th Annual ACM Symposium on Parallel Algorithms, pp. 228-237. ACM, New York (2005) | |||
15. Brodal, G.S., Fagerberg, R.: Cache-oblivious string dictionaries. In: SODA: ACM-SIAM Symposium on Discrete Algorithms, pp. 581-590. ACM Press, New York (2006) | |||
16. Brodal, G.S., Fagerberg, R., Jacob, R.: Cache-oblivious search trees via binary trees of small height. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 39-48 ACM, New York (2002) | |||
17. Franceschini, G., Grossi, R.: Optimal worst-case operations for implicit cache-oblivious search trees. In: Proc. Algorithms and Data Structures, 8th International Workshop, WADS. LNCS, vol. 2748, pp. 114-126. Springer, Berlin (2003) | |||
18. Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 285-298. IEEE Computer Society Press, Los Alamitos (1999) | |||
19. Itai, A., Konheim, A.G., Rodeh, M.: A sparse table implementation of priority queues. In: Automata, Languages and Programming, 8th Colloquium. LNCS, vol. 115, pp. 417-431. Springer, Berlin (1981) | |||
20. Ladner, R.E., Fortna, R., B.-Nguyen, H.: A comparison of cache aware and cache oblivious static search trees using program instrumentation. In: Experimental Algorithmics. LNCS, vol. 2547, pp. 78-92. Springer, Berlin (2000) | |||
21. Prokop, H.: Cache-oblivious algorithms. Master's thesis, Massachusetts Institute of Technology (1999) | |||
22. Rahman, N., Cole, R., Raman, R.: Optimised predecessor data structures for internal memory. In: Proc. Algorithm Engineering, 5th International Workshop, WAE. LNCS, vol. 2141, pp. 67-78. Springer, Berlin (2001) | |||
