License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2023.28
URN: urn:nbn:de:0030-drops-182214
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18221/
Go to the corresponding LIPIcs Volume Portal

Shaikhha, Amir ; Ghorbani, Mahdi ; Shahrokhi, Hesam

Hinted Dictionaries: Efficient Functional Ordered Sets and Maps

pdf-format:
LIPIcs-ECOOP-2023-28.pdf (1 MB)

Abstract

This paper introduces hinted dictionaries for expressing efficient ordered sets and maps functionally. As opposed to the traditional ordered dictionaries with logarithmic operations, hinted dictionaries can achieve better performance by using cursor-like objects referred to as hints. Hinted dictionaries unify the interfaces of imperative ordered dictionaries (e.g., C++ maps) and functional ones (e.g., Adams' sets). We show that such dictionaries can use sorted arrays, unbalanced trees, and balanced trees as their underlying representations. Throughout the paper, we use Scala to present the different components of hinted dictionaries. We also provide a C++ implementation to evaluate the effectiveness of hinted dictionaries. Hinted dictionaries provide superior performance for set-set operations in comparison with the standard library of C++. Also, they show a competitive performance in comparison with the SciPy library for sparse vector operations.

BibTeX - Entry

@InProceedings{shaikhha_et_al:LIPIcs.ECOOP.2023.28,
  author =	{Shaikhha, Amir and Ghorbani, Mahdi and Shahrokhi, Hesam},
  title =	{{Hinted Dictionaries: Efficient Functional Ordered Sets and Maps}},
  booktitle =	{37th European Conference on Object-Oriented Programming (ECOOP 2023)},
  pages =	{28:1--28:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-281-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{263},
  editor =	{Ali, Karim and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18221},
  URN =		{urn:nbn:de:0030-drops-182214},
  doi =		{10.4230/LIPIcs.ECOOP.2023.28},
  annote =	{Keywords: Functional Collections, Ordered Dictionaries, Sparse Linear Algebra}
}

Keywords: Functional Collections, Ordered Dictionaries, Sparse Linear Algebra
Collection: 37th European Conference on Object-Oriented Programming (ECOOP 2023)
Issue Date: 2023
Date of publication: 11.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI