Skip to main content

Home/ Coders/ Group items tagged algorithms

Rss Feed Group items tagged

Fabien Cadet

Algorithms: The Ubiquitous Binary Search | Set 1 | GeeksforGeeks - 9 views

Fabien Cadet

STXXL : Standard Template Library for Extra Large Data Sets - 4 views

  • The key features of STXXL are:

  • Transparent support of parallel disks. The library provides implementations of basic parallel disk algorithms. STXXL is the only external memory algorithm library supporting parallel disks.
  • The library is able to handle problems of very large size (tested to up to dozens of terabytes).
  • ...4 more annotations...
    • Improved utilization of computer resources. STXXL implementations of external memory algorithms and data structures benefit from overlapping of I/O and computation.
    • Small constant factors in I/O volume. A unique library feature called "pipelining" can save more than half the number of I/Os, by streaming data between algorithmic components, instead of temporarily storing them on disk. A development branch supports asynchronous execution of the algorithmic components, enabling high-level task parallelism.
    • Shorter development times due to well known STL-compatible interfaces for external memory algorithms and data structures.
    • For internal computation, parallel algorithms from the MCSTL or the libstdc++ parallel mode are optionally utilized, making the algorithms inherently benefit from multi-core parallelism.

    « The core of STXXL is an implementation of the C++ standard template library STL for external memory (out-of-core) computations, i. e., STXXL implements containers and algorithms that can process huge volumes of data that only fit on disks. »
Fabien Cadet

Shtetl-Optimized » Blog Archive » Fighting Hype with Hype - 2 views

  • In the end, they conclude that NP-complete problems are just as hard on an adiabatic quantum computer as on a classical computer. And, since earlier work showed the equivalence between different variants of quantum computers, that pretty much shuts down the possibility of any quantum computer helping with NP-complete problems.
    [...] quantum computers don't help with NP-complete problems ?
Fabien Cadet

MIT's Introduction to Algorithms, Lectures 22 and 23: Cache Oblivious Algorithms - good... - 0 views

  • Cache-oblivious algorithms should not be confused with cache-aware algorithms. Cache-aware algorithms and data structures explicitly depend on various hardware configuration parameters, such as the cache size. Cache-oblivious algorithms do not depend on any hardware parameters.
  • An example of cache-aware (not cache-oblivious) data structure is a B-Tree that has the explicit parameter B, the size of a node. The main disadvantage of cache-aware algorithms is that they are based on the knowledge of the memory structure and size, which makes it difficult to move implementations from one architecture to another.
    « Cache-oblivious algorithms take into account something that has been ignored in all the lectures so far, particularly, the multilevel memory hierarchy of modern computers. Retrieving items from various levels of memory and cache make up a dominant factor of running time, so for speed it is crucial to minimize these costs. The main idea of cache-oblivious algorithms is to achieve optimal use of caches on all levels of a memory hierarchy without knowledge of their size. »
Joel Bennett

Reservoir Sampling - Gregable - 0 views

    A description of the reservoir sampling algorithm for randomly selecting N items from a collection of unknown size in a single iteration ... including a discussion of how to deal with weighted inputs.
Joel Bennett

Z3: SMT solver - 0 views

1 - 8 of 8
Showing 20 items per page