| |
| |
| <!DOCTYPE html> |
| |
| |
| <html lang="en" data-content_root="" > |
| |
| <head> |
| <meta charset="utf-8" /> |
| <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.19: https://docutils.sourceforge.io/" /> |
| |
| <title>Java Algorithms — Apache Arrow v17.0.0.dev52</title> |
| |
| |
| |
| <script data-cfasync="false"> |
| document.documentElement.dataset.mode = localStorage.getItem("mode") || ""; |
| document.documentElement.dataset.theme = localStorage.getItem("theme") || "light"; |
| </script> |
| |
| <!-- Loaded before other Sphinx assets --> |
| <link href="../_static/styles/theme.css?digest=8d27b9dea8ad943066ae" rel="stylesheet" /> |
| <link href="../_static/styles/bootstrap.css?digest=8d27b9dea8ad943066ae" rel="stylesheet" /> |
| <link href="../_static/styles/pydata-sphinx-theme.css?digest=8d27b9dea8ad943066ae" rel="stylesheet" /> |
| |
| |
| <link href="../_static/vendor/fontawesome/6.5.1/css/all.min.css?digest=8d27b9dea8ad943066ae" rel="stylesheet" /> |
| <link rel="preload" as="font" type="font/woff2" crossorigin href="../_static/vendor/fontawesome/6.5.1/webfonts/fa-solid-900.woff2" /> |
| <link rel="preload" as="font" type="font/woff2" crossorigin href="../_static/vendor/fontawesome/6.5.1/webfonts/fa-brands-400.woff2" /> |
| <link rel="preload" as="font" type="font/woff2" crossorigin href="../_static/vendor/fontawesome/6.5.1/webfonts/fa-regular-400.woff2" /> |
| |
| <link rel="stylesheet" type="text/css" href="../_static/pygments.css" /> |
| <link rel="stylesheet" type="text/css" href="../_static/copybutton.css" /> |
| <link rel="stylesheet" type="text/css" href="../_static/design-style.1e8bd061cd6da7fc9cf755528e8ffc24.min.css" /> |
| <link rel="stylesheet" type="text/css" href="../_static/theme_overrides.css" /> |
| |
| <!-- Pre-loaded scripts that we'll load fully later --> |
| <link rel="preload" as="script" href="../_static/scripts/bootstrap.js?digest=8d27b9dea8ad943066ae" /> |
| <link rel="preload" as="script" href="../_static/scripts/pydata-sphinx-theme.js?digest=8d27b9dea8ad943066ae" /> |
| <script src="../_static/vendor/fontawesome/6.5.1/js/all.min.js?digest=8d27b9dea8ad943066ae"></script> |
| |
| <script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script> |
| <script src="../_static/doctools.js"></script> |
| <script src="../_static/sphinx_highlight.js"></script> |
| <script src="../_static/clipboard.min.js"></script> |
| <script src="../_static/copybutton.js"></script> |
| <script src="../_static/design-tabs.js"></script> |
| <script>DOCUMENTATION_OPTIONS.pagename = 'java/algorithm';</script> |
| <script> |
| DOCUMENTATION_OPTIONS.theme_version = '0.15.2'; |
| DOCUMENTATION_OPTIONS.theme_switcher_json_url = '/docs/_static/versions.json'; |
| DOCUMENTATION_OPTIONS.theme_switcher_version_match = 'dev/'; |
| DOCUMENTATION_OPTIONS.show_version_warning_banner = true; |
| </script> |
| <link rel="canonical" href="https://arrow.apache.org/docs/java/algorithm.html" /> |
| <link rel="icon" href="../_static/favicon.ico"/> |
| <link rel="index" title="Index" href="../genindex.html" /> |
| <link rel="search" title="Search" href="../search.html" /> |
| <link rel="next" title="Arrow Flight RPC" href="flight.html" /> |
| <link rel="prev" title="Reading/Writing IPC formats" href="ipc.html" /> |
| |
| <meta name="viewport" content="width=device-width, initial-scale=1"/> |
| <meta name="docsearch:language" content="en"/> |
| |
| <!-- Matomo --> |
| <script> |
| var _paq = window._paq = window._paq || []; |
| /* tracker methods like "setCustomDimension" should be called before "trackPageView" */ |
| /* We explicitly disable cookie tracking to avoid privacy issues */ |
| _paq.push(['disableCookies']); |
| _paq.push(['trackPageView']); |
| _paq.push(['enableLinkTracking']); |
| (function() { |
| var u="https://analytics.apache.org/"; |
| _paq.push(['setTrackerUrl', u+'matomo.php']); |
| _paq.push(['setSiteId', '20']); |
| var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0]; |
| g.async=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s); |
| })(); |
| </script> |
| <!-- End Matomo Code --> |
| |
| </head> |
| |
| |
| <body data-bs-spy="scroll" data-bs-target=".bd-toc-nav" data-offset="180" data-bs-root-margin="0px 0px -60%" data-default-mode=""> |
| |
| |
| |
| <a id="pst-skip-link" class="skip-link" href="#main-content">Skip to main content</a> |
| |
| <div id="pst-scroll-pixel-helper"></div> |
| |
| <button type="button" class="btn rounded-pill" id="pst-back-to-top"> |
| <i class="fa-solid fa-arrow-up"></i> |
| Back to top |
| </button> |
| |
| |
| <input type="checkbox" |
| class="sidebar-toggle" |
| name="__primary" |
| id="__primary"/> |
| <label class="overlay overlay-primary" for="__primary"></label> |
| |
| <input type="checkbox" |
| class="sidebar-toggle" |
| name="__secondary" |
| id="__secondary"/> |
| <label class="overlay overlay-secondary" for="__secondary"></label> |
| |
| <div class="search-button__wrapper"> |
| <div class="search-button__overlay"></div> |
| <div class="search-button__search-container"> |
| <form class="bd-search d-flex align-items-center" |
| action="../search.html" |
| method="get"> |
| <i class="fa-solid fa-magnifying-glass"></i> |
| <input type="search" |
| class="form-control" |
| name="q" |
| id="search-input" |
| placeholder="Search the docs ..." |
| aria-label="Search the docs ..." |
| autocomplete="off" |
| autocorrect="off" |
| autocapitalize="off" |
| spellcheck="false"/> |
| <span class="search-button__kbd-shortcut"><kbd class="kbd-shortcut__modifier">Ctrl</kbd>+<kbd>K</kbd></span> |
| </form></div> |
| </div> |
| |
| <header class="bd-header navbar navbar-expand-lg bd-navbar"> |
| <div class="bd-header__inner bd-page-width"> |
| <label class="sidebar-toggle primary-toggle" for="__primary"> |
| <span class="fa-solid fa-bars"></span> |
| </label> |
| |
| |
| <div class="col-lg-3 navbar-header-items__start"> |
| |
| <div class="navbar-item"> |
| |
| |
| |
| <a class="navbar-brand logo" href="../index.html"> |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| <img src="../_static/arrow.png" class="logo__image only-light" alt="Apache Arrow v17.0.0.dev52 - Home"/> |
| <script>document.write(`<img src="../_static/arrow-dark.png" class="logo__image only-dark" alt="Apache Arrow v17.0.0.dev52 - Home"/>`);</script> |
| |
| |
| </a></div> |
| |
| </div> |
| |
| <div class="col-lg-9 navbar-header-items"> |
| |
| <div class="me-auto navbar-header-items__center"> |
| |
| <div class="navbar-item"> |
| <nav class="navbar-nav"> |
| <ul class="bd-navbar-elements navbar-nav"> |
| |
| <li class="nav-item"> |
| <a class="nav-link nav-internal" href="../format/index.html"> |
| Specifications |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link nav-internal" href="../developers/index.html"> |
| Development |
| </a> |
| </li> |
| |
| <li class="nav-item dropdown"> |
| <button class="btn dropdown-toggle nav-item" type="button" data-bs-toggle="dropdown" aria-expanded="false" aria-controls="pst-nav-more-links"> |
| Implementations |
| </button> |
| <ul id="pst-nav-more-links" class="dropdown-menu"> |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../c_glib/index.html"> |
| C/GLib |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../cpp/index.html"> |
| C++ |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://github.com/apache/arrow/blob/main/csharp/README.md"> |
| C# |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://pkg.go.dev/github.com/apache/arrow/go/v17"> |
| Go |
| </a> |
| </li> |
| |
| |
| <li class="nav-item current active"> |
| <a class="nav-link dropdown-item nav-internal" href="index.html"> |
| Java |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../js/index.html"> |
| JavaScript |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/julia/"> |
| Julia |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://github.com/apache/arrow/blob/main/matlab/README.md"> |
| MATLAB |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/nanoarrow/"> |
| nanoarrow |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../python/index.html"> |
| Python |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../r/index.html"> |
| R |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://github.com/apache/arrow/blob/main/ruby/README.md"> |
| Ruby |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://docs.rs/crate/arrow/"> |
| Rust |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../status.html"> |
| Implementation Status |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/cookbook/cpp/"> |
| C++ cookbook |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/cookbook/java/"> |
| Java cookbook |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/cookbook/py/"> |
| Python cookbook |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/cookbook/r/"> |
| R cookbook |
| </a> |
| </li> |
| |
| </ul> |
| </li> |
| |
| </ul> |
| </nav></div> |
| |
| </div> |
| |
| |
| <div class="navbar-header-items__end"> |
| |
| <div class="navbar-item navbar-persistent--container"> |
| |
| |
| <script> |
| document.write(` |
| <button class="btn navbar-btn search-button-field search-button__button" title="Search" aria-label="Search" data-bs-placement="bottom" data-bs-toggle="tooltip"> |
| <i class="fa-solid fa-magnifying-glass"></i> |
| <span class="search-button__default-text">Search</span> |
| <span class="search-button__kbd-shortcut"><kbd class="kbd-shortcut__modifier">Ctrl</kbd>+<kbd class="kbd-shortcut__modifier">K</kbd></span> |
| </button> |
| `); |
| </script> |
| </div> |
| |
| |
| <div class="navbar-item"> |
| <script> |
| document.write(` |
| <div class="version-switcher__container dropdown"> |
| <button id="pst-version-switcher-button-2" |
| type="button" |
| class="version-switcher__button btn btn-sm navbar-btn dropdown-toggle" |
| data-bs-toggle="dropdown" |
| aria-haspopup="listbox" |
| aria-controls="pst-version-switcher-list-2" |
| aria-label="Version switcher list" |
| > |
| Choose version <!-- this text may get changed later by javascript --> |
| <span class="caret"></span> |
| </button> |
| <div id="pst-version-switcher-list-2" |
| class="version-switcher__menu dropdown-menu list-group-flush py-0" |
| role="listbox" aria-labelledby="pst-version-switcher-button-2"> |
| <!-- dropdown will be populated by javascript on page load --> |
| </div> |
| </div> |
| `); |
| </script></div> |
| |
| <div class="navbar-item"> |
| |
| <script> |
| document.write(` |
| <button class="btn btn-sm navbar-btn theme-switch-button" title="light/dark" aria-label="light/dark" data-bs-placement="bottom" data-bs-toggle="tooltip"> |
| <span class="theme-switch nav-link" data-mode="light"><i class="fa-solid fa-sun fa-lg"></i></span> |
| <span class="theme-switch nav-link" data-mode="dark"><i class="fa-solid fa-moon fa-lg"></i></span> |
| <span class="theme-switch nav-link" data-mode="auto"><i class="fa-solid fa-circle-half-stroke fa-lg"></i></span> |
| </button> |
| `); |
| </script></div> |
| |
| <div class="navbar-item"><ul class="navbar-icon-links navbar-nav" |
| aria-label="Icon Links"> |
| <li class="nav-item"> |
| |
| |
| |
| |
| |
| |
| |
| |
| <a href="https://github.com/apache/arrow" title="GitHub" class="nav-link" rel="noopener" target="_blank" data-bs-toggle="tooltip" data-bs-placement="bottom"><span><i class="fa-brands fa-square-github fa-lg" aria-hidden="true"></i></span> |
| <span class="sr-only">GitHub</span></a> |
| </li> |
| <li class="nav-item"> |
| |
| |
| |
| |
| |
| |
| |
| |
| <a href="https://twitter.com/ApacheArrow" title="X" class="nav-link" rel="noopener" target="_blank" data-bs-toggle="tooltip" data-bs-placement="bottom"><span><i class="fa-brands fa-square-x-twitter fa-lg" aria-hidden="true"></i></span> |
| <span class="sr-only">X</span></a> |
| </li> |
| </ul></div> |
| |
| </div> |
| |
| </div> |
| |
| |
| <div class="navbar-persistent--mobile"> |
| |
| <script> |
| document.write(` |
| <button class="btn navbar-btn search-button-field search-button__button" title="Search" aria-label="Search" data-bs-placement="bottom" data-bs-toggle="tooltip"> |
| <i class="fa-solid fa-magnifying-glass"></i> |
| <span class="search-button__default-text">Search</span> |
| <span class="search-button__kbd-shortcut"><kbd class="kbd-shortcut__modifier">Ctrl</kbd>+<kbd class="kbd-shortcut__modifier">K</kbd></span> |
| </button> |
| `); |
| </script> |
| </div> |
| |
| |
| |
| <label class="sidebar-toggle secondary-toggle" for="__secondary" tabindex="0"> |
| <span class="fa-solid fa-outdent"></span> |
| </label> |
| |
| </div> |
| |
| </header> |
| |
| |
| <div class="bd-container"> |
| <div class="bd-container__inner bd-page-width"> |
| |
| |
| |
| <div class="bd-sidebar-primary bd-sidebar"> |
| |
| |
| |
| <div class="sidebar-header-items sidebar-primary__section"> |
| |
| |
| <div class="sidebar-header-items__center"> |
| |
| <div class="navbar-item"> |
| <nav class="navbar-nav"> |
| <ul class="bd-navbar-elements navbar-nav"> |
| |
| <li class="nav-item"> |
| <a class="nav-link nav-internal" href="../format/index.html"> |
| Specifications |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link nav-internal" href="../developers/index.html"> |
| Development |
| </a> |
| </li> |
| |
| <li class="nav-item dropdown"> |
| <button class="btn dropdown-toggle nav-item" type="button" data-bs-toggle="dropdown" aria-expanded="false" aria-controls="pst-nav-more-links-2"> |
| Implementations |
| </button> |
| <ul id="pst-nav-more-links-2" class="dropdown-menu"> |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../c_glib/index.html"> |
| C/GLib |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../cpp/index.html"> |
| C++ |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://github.com/apache/arrow/blob/main/csharp/README.md"> |
| C# |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://pkg.go.dev/github.com/apache/arrow/go/v17"> |
| Go |
| </a> |
| </li> |
| |
| |
| <li class="nav-item current active"> |
| <a class="nav-link dropdown-item nav-internal" href="index.html"> |
| Java |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../js/index.html"> |
| JavaScript |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/julia/"> |
| Julia |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://github.com/apache/arrow/blob/main/matlab/README.md"> |
| MATLAB |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/nanoarrow/"> |
| nanoarrow |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../python/index.html"> |
| Python |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../r/index.html"> |
| R |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://github.com/apache/arrow/blob/main/ruby/README.md"> |
| Ruby |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://docs.rs/crate/arrow/"> |
| Rust |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-internal" href="../status.html"> |
| Implementation Status |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/cookbook/cpp/"> |
| C++ cookbook |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/cookbook/java/"> |
| Java cookbook |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/cookbook/py/"> |
| Python cookbook |
| </a> |
| </li> |
| |
| |
| <li class="nav-item"> |
| <a class="nav-link dropdown-item nav-external" href="https://arrow.apache.org/cookbook/r/"> |
| R cookbook |
| </a> |
| </li> |
| |
| </ul> |
| </li> |
| |
| </ul> |
| </nav></div> |
| |
| </div> |
| |
| |
| |
| <div class="sidebar-header-items__end"> |
| |
| <div class="navbar-item"> |
| <script> |
| document.write(` |
| <div class="version-switcher__container dropdown"> |
| <button id="pst-version-switcher-button-3" |
| type="button" |
| class="version-switcher__button btn btn-sm navbar-btn dropdown-toggle" |
| data-bs-toggle="dropdown" |
| aria-haspopup="listbox" |
| aria-controls="pst-version-switcher-list-3" |
| aria-label="Version switcher list" |
| > |
| Choose version <!-- this text may get changed later by javascript --> |
| <span class="caret"></span> |
| </button> |
| <div id="pst-version-switcher-list-3" |
| class="version-switcher__menu dropdown-menu list-group-flush py-0" |
| role="listbox" aria-labelledby="pst-version-switcher-button-3"> |
| <!-- dropdown will be populated by javascript on page load --> |
| </div> |
| </div> |
| `); |
| </script></div> |
| |
| <div class="navbar-item"> |
| |
| <script> |
| document.write(` |
| <button class="btn btn-sm navbar-btn theme-switch-button" title="light/dark" aria-label="light/dark" data-bs-placement="bottom" data-bs-toggle="tooltip"> |
| <span class="theme-switch nav-link" data-mode="light"><i class="fa-solid fa-sun fa-lg"></i></span> |
| <span class="theme-switch nav-link" data-mode="dark"><i class="fa-solid fa-moon fa-lg"></i></span> |
| <span class="theme-switch nav-link" data-mode="auto"><i class="fa-solid fa-circle-half-stroke fa-lg"></i></span> |
| </button> |
| `); |
| </script></div> |
| |
| <div class="navbar-item"><ul class="navbar-icon-links navbar-nav" |
| aria-label="Icon Links"> |
| <li class="nav-item"> |
| |
| |
| |
| |
| |
| |
| |
| |
| <a href="https://github.com/apache/arrow" title="GitHub" class="nav-link" rel="noopener" target="_blank" data-bs-toggle="tooltip" data-bs-placement="bottom"><span><i class="fa-brands fa-square-github fa-lg" aria-hidden="true"></i></span> |
| <span class="sr-only">GitHub</span></a> |
| </li> |
| <li class="nav-item"> |
| |
| |
| |
| |
| |
| |
| |
| |
| <a href="https://twitter.com/ApacheArrow" title="X" class="nav-link" rel="noopener" target="_blank" data-bs-toggle="tooltip" data-bs-placement="bottom"><span><i class="fa-brands fa-square-x-twitter fa-lg" aria-hidden="true"></i></span> |
| <span class="sr-only">X</span></a> |
| </li> |
| </ul></div> |
| |
| </div> |
| |
| </div> |
| |
| <div class="sidebar-primary-items__start sidebar-primary__section"> |
| <div class="sidebar-primary-item"> |
| <nav class="bd-docs-nav bd-links" |
| aria-label="Section Navigation"> |
| <p class="bd-links__title" role="heading" aria-level="1">Section Navigation</p> |
| <div class="bd-toc-item navbar-nav"><ul class="current nav bd-sidenav"> |
| <li class="toctree-l1"><a class="reference internal" href="quickstartguide.html">Quick Start Guide</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="overview.html">High-Level Overview</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="install.html">Installing Java Modules</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="memory.html">Memory Management</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="vector.html">ValueVector</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="vector_schema_root.html">Tabular Data</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="table.html">Table</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="ipc.html">Reading/Writing IPC formats</a></li> |
| <li class="toctree-l1 current active"><a class="current reference internal" href="#">Java Algorithms</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="flight.html">Arrow Flight RPC</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="flight_sql.html">Arrow Flight SQL</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="flight_sql_jdbc_driver.html">Arrow Flight SQL JDBC Driver</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="dataset.html">Dataset</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="substrait.html">Substrait</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="cdata.html">C Data Interface</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="jdbc.html">Arrow JDBC Adapter</a></li> |
| <li class="toctree-l1"><a class="reference internal" href="reference/index.html">Reference (javadoc)</a></li> |
| <li class="toctree-l1"><a class="reference external" href="https://arrow.apache.org/cookbook/java/">Java cookbook</a></li> |
| </ul> |
| </div> |
| </nav></div> |
| </div> |
| |
| |
| <div class="sidebar-primary-items__end sidebar-primary__section"> |
| </div> |
| |
| <div id="rtd-footer-container"></div> |
| |
| |
| </div> |
| |
| <main id="main-content" class="bd-main"> |
| |
| |
| <div class="bd-content"> |
| <div class="bd-article-container"> |
| |
| <div class="bd-header-article"> |
| <div class="header-article-items header-article__inner"> |
| |
| <div class="header-article-items__start"> |
| |
| <div class="header-article-item"> |
| |
| |
| |
| <nav aria-label="Breadcrumb"> |
| <ul class="bd-breadcrumbs"> |
| |
| <li class="breadcrumb-item breadcrumb-home"> |
| <a href="../index.html" class="nav-link" aria-label="Home"> |
| <i class="fa-solid fa-home"></i> |
| </a> |
| </li> |
| |
| <li class="breadcrumb-item"><a href="index.html" class="nav-link">Java Implementation</a></li> |
| |
| <li class="breadcrumb-item active" aria-current="page">Java Algorithms</li> |
| </ul> |
| </nav> |
| </div> |
| |
| </div> |
| |
| |
| </div> |
| </div> |
| |
| |
| |
| |
| <div id="searchbox"></div> |
| <article class="bd-article"> |
| |
| <section id="java-algorithms"> |
| <h1>Java Algorithms<a class="headerlink" href="#java-algorithms" title="Permalink to this heading">#</a></h1> |
| <p>Arrow’s Java library provides algorithms for some commonly-used |
| functionalities. The algorithms are provided in the <code class="docutils literal notranslate"><span class="pre">org.apache.arrow.algorithm</span></code> |
| package of the <code class="docutils literal notranslate"><span class="pre">algorithm</span></code> module.</p> |
| <section id="comparing-vector-elements"> |
| <h2>Comparing Vector Elements<a class="headerlink" href="#comparing-vector-elements" title="Permalink to this heading">#</a></h2> |
| <p>Comparing vector elements is the basic for many algorithms. Vector |
| elements can be compared in one of the two ways:</p> |
| <p>1. <strong>Equality comparison</strong>: there are two possible results for this type of comparisons: <code class="docutils literal notranslate"><span class="pre">equal</span></code> and <code class="docutils literal notranslate"><span class="pre">unequal</span></code>. |
| Currently, this type of comparison is supported through the <code class="docutils literal notranslate"><span class="pre">org.apache.arrow.vector.compare.VectorValueEqualizer</span></code> |
| interface.</p> |
| <p>2. <strong>Ordering comparison</strong>: there are three possible results for this type of comparisons: <code class="docutils literal notranslate"><span class="pre">less</span> <span class="pre">than</span></code>, <code class="docutils literal notranslate"><span class="pre">equal</span> <span class="pre">to</span></code> |
| and <code class="docutils literal notranslate"><span class="pre">greater</span> <span class="pre">than</span></code>. This comparison is supported by the abstract class <code class="docutils literal notranslate"><span class="pre">org.apache.arrow.algorithm.sort.VectorValueComparator</span></code>.</p> |
| <p>We provide default implementations to compare vector elements. However, users can also define ways |
| for customized comparisons.</p> |
| </section> |
| <section id="vector-element-search"> |
| <h2>Vector Element Search<a class="headerlink" href="#vector-element-search" title="Permalink to this heading">#</a></h2> |
| <p>A search algorithm tries to find a particular value in a vector. When successful, a vector index is |
| returned; otherwise, a <code class="docutils literal notranslate"><span class="pre">-1</span></code> is returned. The following search algorithms are provided:</p> |
| <p>1. <strong>Linear search</strong>: this algorithm simply traverses the vector from the beginning, until a match is |
| found, or the end of the vector is reached. So it takes <code class="docutils literal notranslate"><span class="pre">O(n)</span></code> time, where <code class="docutils literal notranslate"><span class="pre">n</span></code> is the number of elements |
| in the vector. This algorithm is implemented in <code class="docutils literal notranslate"><span class="pre">org.apache.arrow.algorithm.search.VectorSearcher#linearSearch</span></code>.</p> |
| <p>2. <strong>Binary search</strong>: this represents a more efficient search algorithm, as it runs in <code class="docutils literal notranslate"><span class="pre">O(log(n))</span></code> time. |
| However, it is only applicable to sorted vectors. To get a sorted vector, |
| one can use one of our sorting algorithms, which will be discussed in the next section. This algorithm |
| is implemented in <code class="docutils literal notranslate"><span class="pre">org.apache.arrow.algorithm.search.VectorSearcher#binarySearch</span></code>.</p> |
| <p>3. <strong>Parallel search</strong>: when the vector is large, it takes a long time to traverse the elements to search |
| for a value. To make this process faster, one can split the vector into multiple partitions, and perform the |
| search for each partition in parallel. This is supported by <code class="docutils literal notranslate"><span class="pre">org.apache.arrow.algorithm.search.ParallelSearcher</span></code>.</p> |
| <p>4. <strong>Range search</strong>: for many scenarios, there can be multiple matching values in the vector. |
| If the vector is sorted, the matching values reside in a contiguous region in the vector. The |
| range search algorithm tries to find the upper/lower bound of the region in <code class="docutils literal notranslate"><span class="pre">O(log(n))</span></code> time. |
| An implementation is provided in <code class="docutils literal notranslate"><span class="pre">org.apache.arrow.algorithm.search.VectorRangeSearcher</span></code>.</p> |
| </section> |
| <section id="vector-sorting"> |
| <h2>Vector Sorting<a class="headerlink" href="#vector-sorting" title="Permalink to this heading">#</a></h2> |
| <p>Given a vector, a sorting algorithm turns it into a sorted one. The sorting criteria must |
| be specified by some ordering comparison operation. The sorting algorithms can be |
| classified into the following categories:</p> |
| <p>1. <strong>In-place sorter</strong>: an in-place sorter performs the sorting by manipulating the original |
| vector, without creating any new vector. So it just returns the original vector after the sorting operations. |
| Currently, we have <code class="docutils literal notranslate"><span class="pre">org.apache.arrow.algorithm.sort.FixedWidthInPlaceVectorSorter</span></code> for in-place |
| sorting in <code class="docutils literal notranslate"><span class="pre">O(nlog(n))</span></code> time. As the name suggests, it only supports fixed width vectors.</p> |
| <p>2. <strong>Out-of-place sorter</strong>: an out-of-place sorter does not mutate the original vector. Instead, |
| it copies vector elements to a new vector in sorted order, and returns the new vector. |
| We have <code class="docutils literal notranslate"><span class="pre">org.apache.arrow.algorithm.sort.FixedWidthInPlaceVectorSorter.FixedWidthOutOfPlaceVectorSorter</span></code> |
| and <code class="docutils literal notranslate"><span class="pre">org.apache.arrow.algorithm.sort.FixedWidthInPlaceVectorSorter.VariableWidthOutOfPlaceVectorSorter</span></code> |
| for fixed width and variable width vectors, respectively. Both algorithms run in <code class="docutils literal notranslate"><span class="pre">O(nlog(n))</span></code> time.</p> |
| <p>3. <strong>Index sorter</strong>: this sorter does not actually sort the vector. Instead, it returns an integer |
| vector, which correspond to indices of vector elements in sorted order. With the index vector, one can |
| easily construct a sorted vector. In addition, some other tasks can be easily achieved, like finding the <code class="docutils literal notranslate"><span class="pre">k``th</span> |
| <span class="pre">smallest</span> <span class="pre">value</span> <span class="pre">in</span> <span class="pre">the</span> <span class="pre">vector.</span> <span class="pre">Index</span> <span class="pre">sorting</span> <span class="pre">is</span> <span class="pre">supported</span> <span class="pre">by</span> <span class="pre">``org.apache.arrow.algorithm.sort.IndexSorter</span></code>, |
| which runs in <code class="docutils literal notranslate"><span class="pre">O(nlog(n))</span></code> time. It is applicable to vectors of any type.</p> |
| </section> |
| <section id="other-algorithms"> |
| <h2>Other Algorithms<a class="headerlink" href="#other-algorithms" title="Permalink to this heading">#</a></h2> |
| <p>Other algorithms include vector deduplication, dictionary encoding, etc., in the <code class="docutils literal notranslate"><span class="pre">algorithm</span></code> module.</p> |
| </section> |
| </section> |
| |
| |
| </article> |
| |
| |
| |
| |
| |
| <footer class="prev-next-footer"> |
| |
| <div class="prev-next-area"> |
| <a class="left-prev" |
| href="ipc.html" |
| title="previous page"> |
| <i class="fa-solid fa-angle-left"></i> |
| <div class="prev-next-info"> |
| <p class="prev-next-subtitle">previous</p> |
| <p class="prev-next-title">Reading/Writing IPC formats</p> |
| </div> |
| </a> |
| <a class="right-next" |
| href="flight.html" |
| title="next page"> |
| <div class="prev-next-info"> |
| <p class="prev-next-subtitle">next</p> |
| <p class="prev-next-title">Arrow Flight RPC</p> |
| </div> |
| <i class="fa-solid fa-angle-right"></i> |
| </a> |
| </div> |
| </footer> |
| |
| </div> |
| |
| |
| |
| <div class="bd-sidebar-secondary bd-toc"><div class="sidebar-secondary-items sidebar-secondary__inner"> |
| |
| |
| <div class="sidebar-secondary-item"> |
| <div |
| id="pst-page-navigation-heading-2" |
| class="page-toc tocsection onthispage"> |
| <i class="fa-solid fa-list"></i> On this page |
| </div> |
| <nav class="bd-toc-nav page-toc" aria-labelledby="pst-page-navigation-heading-2"> |
| <ul class="visible nav section-nav flex-column"> |
| <li class="toc-h2 nav-item toc-entry"><a class="reference internal nav-link" href="#comparing-vector-elements">Comparing Vector Elements</a></li> |
| <li class="toc-h2 nav-item toc-entry"><a class="reference internal nav-link" href="#vector-element-search">Vector Element Search</a></li> |
| <li class="toc-h2 nav-item toc-entry"><a class="reference internal nav-link" href="#vector-sorting">Vector Sorting</a></li> |
| <li class="toc-h2 nav-item toc-entry"><a class="reference internal nav-link" href="#other-algorithms">Other Algorithms</a></li> |
| </ul> |
| </nav></div> |
| |
| <div class="sidebar-secondary-item"> |
| |
| |
| <div class="tocsection editthispage"> |
| <a href="https://github.com/apache/arrow/edit/main/docs/source/java/algorithm.rst"> |
| <i class="fa-solid fa-pencil"></i> |
| |
| |
| |
| Edit on GitHub |
| |
| |
| </a> |
| </div> |
| </div> |
| |
| </div></div> |
| |
| |
| </div> |
| <footer class="bd-footer-content"> |
| |
| </footer> |
| |
| </main> |
| </div> |
| </div> |
| |
| <!-- Scripts loaded after <body> so the DOM is not blocked --> |
| <script src="../_static/scripts/bootstrap.js?digest=8d27b9dea8ad943066ae"></script> |
| <script src="../_static/scripts/pydata-sphinx-theme.js?digest=8d27b9dea8ad943066ae"></script> |
| |
| <footer class="bd-footer"> |
| <div class="bd-footer__inner bd-page-width"> |
| |
| <div class="footer-items__start"> |
| |
| <div class="footer-item"> |
| |
| <p class="copyright"> |
| |
| © Copyright 2016-2024 Apache Software Foundation. |
| Apache Arrow, Arrow, Apache, the Apache feather logo, and the Apache Arrow project logo are either registered trademarks or trademarks of The Apache Software Foundation in the United States and other countries. |
| <br/> |
| |
| </p> |
| </div> |
| |
| <div class="footer-item"> |
| |
| <p class="sphinx-version"> |
| Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 6.2.0. |
| <br/> |
| </p> |
| </div> |
| |
| </div> |
| |
| |
| |
| <div class="footer-items__end"> |
| |
| <div class="footer-item"> |
| <p class="theme-version"> |
| Built with the <a href="https://pydata-sphinx-theme.readthedocs.io/en/stable/index.html">PyData Sphinx Theme</a> 0.15.2. |
| </p></div> |
| |
| </div> |
| |
| </div> |
| |
| </footer> |
| </body> |
| </html> |
