Misplaced Pages

#912087

61-527: Deque is sometimes written dequeue , but this use is generally deprecated in technical literature or technical writing because dequeue is also a verb meaning "to remove from a queue". Nevertheless, several libraries and some writers, such as Aho , Hopcroft , and Ullman in their textbook Data Structures and Algorithms , spell it dequeue . John Mitchell , author of Concepts in Programming Languages, also uses this terminology. This differs from

122-414: A library is a collection of resources that is leveraged during software development to implement a computer program . Historically, a library consisted of subroutines (generally called functions today). The concept now includes other forms of executable code including classes and non-executable data including images and text . It can also refer to a collection of source code . For example,

183-402: A modular fashion. When writing code that uses a library, a programmer only needs to know high-level information such as what items it contains at and how to use the items – not all of the internal details of the library. Libraries can use other libraries resulting in a hierarchy of libraries in a program. A library of executable code has a well-defined interface by which the functionality

244-399: A purely functional data structure . Two versions of the implementation exist. The first one, called ' real-time deque , is presented below. It allows the queue to be persistent with operations in O (1) worst-case time, but requires lazy lists with memoization . The second one, with no lazy lists nor memoization is presented at the end of the sections. Its amortized time is O (1) if

305-462: A Communication Pool (COMPOOL), roughly a library of header files. Another major contributor to the modern library concept came in the form of the subprogram innovation of FORTRAN . FORTRAN subprograms can be compiled independently of each other, but the compiler lacked a linker . So prior to the introduction of modules in Fortran-90, type checking between FORTRAN subprograms was impossible. By

366-442: A broader but still restricted fashion. Mihaescu and Tarjan created a simpler (but still highly complex) strictly purely functional implementation of catenable deques, and also a much simpler implementation of strictly purely functional non-catenable deques, both of which have optimal worst-case bounds. Rust's std::collections includes VecDeque which implements a double-ended queue using a growable ring buffer. One example where

427-432: A deque can be used is the work stealing algorithm . This algorithm implements task scheduling for several processors. A separate deque with threads to be executed is maintained for each processor. To execute the next thread, the processor gets the first element from the deque (using the "remove first element" deque operation). If the current thread forks, it is put back to the front of the deque ("insert element at front") and

488-462: A double-ended queue contains n elements in the front list and n elements in the rear list, then the inequality invariant remains satisfied after i insertions and d deletions when (i+d) ≤ n/2 . That is, at most n/2 operations can happen between each rebalancing. Let us first give an implementation of the various operations that affect the front of the deque - cons, head and tail. Those implementations do not necessarily respect

549-460: A dynamic array of size 4, we could push 4 elements onto it, and each operation would take constant time . Yet pushing a fifth element onto that array would take longer as the array would have to create a new array of double the current size (8), copy the old elements onto the new array, and then add the new element. The next three push operations would similarly take constant time, and then the subsequent addition would require another slow doubling of

610-559: A feature called smart linking whereby the linker is aware of or integrated with the compiler, such that the linker knows how external references are used, and code in a library that is never actually used , even though internally referenced, can be discarded from the compiled application. For example, a program that only uses integers for arithmetic, or does no arithmetic operations at all, can exclude floating-point library routines. This smart-linking feature can lead to smaller application file sizes and reduced memory usage. Some references in

671-567: A long time, thus "amortizing" its cost. There are generally three methods for performing amortized analysis: the aggregate method, the accounting method , and the potential method . All of these give correct answers; the choice of which to use depends on which is most convenient for a particular situation. Consider a dynamic array that grows in size as more elements are added to it, such as ArrayList in Java or std::vector in C++. If we started out with

SECTION 10

#1732855329913

732-438: A new thread is executed. When one of the processors finishes execution of its own threads (i.e. its deque is empty), it can "steal" a thread from another processor: it gets the last element from the deque of another processor ("remove last element") and executes it. The work stealing algorithm is used by Intel's Threading Building Blocks (TBB) library for parallel programming. Library (computing) In computer science ,

793-436: A program are loaded from individual shared objects into memory at load time or runtime , rather than being copied by a linker when it creates a single monolithic executable file for the program. Shared libraries can be statically linked during compile-time, meaning that references to the library modules are resolved and the modules are allocated memory when the executable file is created. But often linking of shared libraries

854-466: A program could use a library to indirectly make system calls instead of making those system calls directly in the program. A library can be used by multiple, independent consumers (programs and other libraries). This differs from resources defined in a program which can usually only be used by that program. When a consumer uses a library resource, it gains the value of the library without having to implement it itself. Libraries encourage code reuse in

915-589: A program or library module are stored in a relative or symbolic form which cannot be resolved until all code and libraries are assigned final static addresses. Relocation is the process of adjusting these references, and is done either by the linker or the loader . In general, relocation cannot be done to individual libraries themselves because the addresses in memory may vary depending on the program using them and other libraries they are combined with. Position-independent code avoids references to absolute addresses and therefore does not require relocation. When linking

976-418: A significant cost in resources, whereas other situations may not be as costly. The amortized analysis considers both the costly and less costly operations together over the whole sequence of operations. This may include accounting for different types of input, length of the input, and other factors that affect its performance. Amortized analysis initially emerged from a method called aggregate analysis, which

1037-407: A suffix of .a ( archive , static library) or of .so (shared object, dynamically linked library). Some systems might have multiple names for a dynamically linked library. These names typically share the same prefix and have different suffixes indicating the version number. Most of the names are names for symbolic links to the latest version. For example, on some systems libfoo.so.2 would be

1098-463: A variant of a dynamic array that can grow from both ends, sometimes called array deques . These array deques have all the properties of a dynamic array, such as constant-time random access , good locality of reference , and inefficient insertion/removal in the middle, with the addition of amortized constant-time insertion/removal at both ends, instead of just one end. Three common implementations include: Double-ended queues can also be implemented as

1159-421: Is a function that returns the front, followed by the middle reversed, followed by the rear. This function is also defined using laziness to ensure that it can be computed step by step, with one step executed during each insert' and tail' and taking a constant time. This function uses the invariant that |rear|-2|front| is 2 or 3. where ++ is the function concatenating two lists. Note that, without

1220-440: Is created (static linking), or whenever the program is used at runtime (dynamic linking). The references being resolved may be addresses for jumps and other routine calls. They may be in the main program, or in one module depending upon another. They are resolved into fixed or relocatable addresses (from a common base) by allocating runtime memory for the memory segments of each module referenced. Some programming languages use

1281-413: Is invoked. For example, in C , a library function is invoked via C's normal function call capability. The linker generates code to call a function via the library mechanism if the function is available from a library instead of from the program itself. The functions of a library can be connected to the invoking program at different program lifecycle phases . If the code of the library is accessed during

SECTION 20

#1732855329913

1342-413: Is now subsumed by amortized analysis. The technique was first formally introduced by Robert Tarjan in his 1985 paper Amortized Computational Complexity , which addressed the need for a more useful form of analysis than the common probabilistic methods used. Amortization was initially used for very specific types of algorithms, particularly those involving binary trees and union operations. However, it

1403-399: Is now ubiquitous and comes into play when analyzing many other algorithms as well. Amortized analysis requires knowledge of which series of operations are possible. This is most commonly the case with data structures , which have state that persists between operations. The basic idea is that a worst-case operation can alter the state in such a way that the worst case cannot occur again for

1464-430: Is performed during the creation of an executable or another object file, it is known as static linking or early binding . In this case, the linking is usually done by a linker , but may also be done by the compiler . A static library , also known as an archive , is one intended to be statically linked. Originally, only static libraries existed. Static linking must be performed when any modules are recompiled. All of

1525-500: Is postponed until they are loaded. Although originally pioneered in the 1960s, dynamic linking did not reach the most commonly-used operating systems until the late 1980s. It was generally available in some form in most operating systems by the early 1990s. During this same period, object-oriented programming (OOP) was becoming a significant part of the programming landscape. OOP with runtime binding requires additional information that traditional libraries do not supply. In addition to

1586-441: Is that looking at the worst-case run time can be too pessimistic. Instead, amortized analysis averages the running times of operations in a sequence over that sequence. As a conclusion: "Amortized analysis is a useful tool that complements other techniques such as worst-case and average-case analysis." For a given operation of an algorithm, certain situations (e.g., input parametrizations or data structure contents) may imply

1647-403: Is the current length of the input array. After copying n elements from input, we can perform n dequeue operations, each taking constant time, before the output array is empty again. Thus, we can perform a sequence of n dequeue operations in only ⁠ O ( n ) {\displaystyle O(n)} ⁠ time, which implies that the amortized time of each dequeue operation

1708-496: The ArrayDeque , contrary to its name, does not support random access. Javascript's Array prototype & Perl 's arrays have native support for both removing ( shift and pop ) and adding ( unshift and push ) elements on both ends. Python 2.4 introduced the collections module with support for deque objects . It is implemented using a doubly linked list of fixed-length subarrays. As of PHP 5.3, PHP's SPL extension contains

1769-590: The UNIX world, which uses different file extensions, when linking against .LIB file in Windows one must first know if it is a regular static library or an import library. In the latter case, a .DLL file must be present at runtime. Amortized analysis In computer science , amortized analysis is a method for analyzing a given algorithm's complexity , or how much of a resource, especially time or memory, it takes to execute . The motivation for amortized analysis

1830-576: The 'SplDoublyLinkedList' class that can be used to implement Deque datastructures. Previously to make a Deque structure the array functions array_shift/unshift/pop/push had to be used instead. GHC 's Data.Sequence module implements an efficient, functional deque structure in Haskell . The implementation uses 2–3 finger trees annotated with sizes. There are other (fast) possibilities to implement purely functional (thus also persistent ) double queues (most using heavily lazy evaluation ). Kaplan and Tarjan were

1891-416: The array size. In general, for an arbitrary number n {\displaystyle n} of pushes to an array of any initial size, the times for steps that double the array add in a geometric series to O ( n ) {\displaystyle O(n)} , while the constant times for each remaining push also add to O ( n ) {\displaystyle O(n)} . Therefore

Double-ended queue - Misplaced Pages Continue

1952-439: The average time per push operation is O ( n ) / n = O ( 1 ) {\displaystyle O(n)/n=O(1)} . This reasoning can be formalized and generalized to more complicated data structures using amortized analysis. Shown is a Python3 implementation of a Queue , a FIFO data structure : The enqueue operation just pushes an element onto the input array; this operation does not depend on

2013-514: The build of the invoking program, then the library is called a static library . An alternative is to build the program executable to be separate from the library file. The library functions are connected after the executable is started, either at load-time or runtime . In this case, the library is called a dynamic library . Most compiled languages have a standard library , although programmers can also create their own custom libraries. Most modern software systems provide libraries that implement

2074-457: The class templates std::deque and std::list , for the multiple array and linked list implementations, respectively. As of Java 6, Java's Collections Framework provides a new Deque interface that provides the functionality of insertion and removal at both ends. It is implemented by classes such as ArrayDeque (also new in Java 6) and LinkedList , providing the dynamic array and linked list implementations, respectively. However,

2135-552: The dependencies to external libraries in build configuration files (such as a Maven Pom in Java). Another library technique uses completely separate executables (often in some lightweight form) and calls them using a remote procedure call (RPC) over a network to another computer. This maximizes operating system re-use: the code needed to support the library is the same code being used to provide application support and security for every other program. Additionally, such systems do not require

2196-529: The engine would have a library of its own." In 1947 Goldstine and von Neumann speculated that it would be useful to create a "library" of subroutines for their work on the IAS machine , an early computer that was not yet operational at that time. They envisioned a physical library of magnetic wire recordings , with each wire storing reusable computer code. Inspired by von Neumann, Wilkes and his team constructed EDSAC . A filing cabinet of punched tape held

2257-536: The filename for the second major interface revision of the dynamically linked library libfoo . The .la files sometimes found in the library directories are libtool archives, not usable by the system as such. The system inherits static library conventions from BSD , with the library stored in a .a file, and can use .so -style dynamically linked libraries (with the .dylib suffix instead). Most libraries in macOS, however, consist of "frameworks", placed inside special directories called " bundles " which wrap

2318-403: The first i elements of l , respectively. Or, if |l| < i , they return the empty list and l respectively. A double-ended queue is represented as a sextuple (len_front, front, tail_front, len_rear, rear, tail_rear) where front is a linked list which contains the front of the queue of length len_front . Similarly, rear is a linked list which represents the reverse of

2379-513: The first to implement optimal confluently persistent catenable deques. Their implementation was strictly purely functional in the sense that it did not use lazy evaluation. Okasaki simplified the data structure by using lazy evaluation with a bootstrapped data structure and degrading the performance bounds from worst-case to amortized. Kaplan, Okasaki, and Tarjan produced a simpler, non-bootstrapped, amortized version that can be implemented either using lazy evaluation or more efficiently using mutation in

2440-439: The instantiated objects residing only in memory (although potentially able to be made persistent in separate files). In others, like Smalltalk , the class libraries are merely the starting point for a system image that includes the entire state of the environment, classes and all instantiated objects. Today most class libraries are stored in a package repository (such as Maven Central for Java). Client code explicitly declare

2501-434: The invariant. In a second time we'll explain how to modify a deque which does not satisfy the invariant into one which satisfies it. However, they use the invariant, in that if the front is empty then the rear has at most one element. The operations affecting the rear of the list are defined similarly by symmetry. It remains to explain how to define a method balance that rebalance the deque if insert' or tail broke

Double-ended queue - Misplaced Pages Continue

2562-703: The invariant. The method insert and tail can be defined by first applying insert' and tail' and then applying balance . where rotateDrop(front, i, rear)) return the concatenation of front and of drop(i, rear) . That is front' = rotateDrop(front, ceil_half_len, rear) put into front' the content of front and the content of rear that is not already in rear' . Since dropping n elements takes O ( n ) {\displaystyle O(n)} time, we use laziness to ensure that elements are dropped two by two, with two drops being done during each tail' and each insert' operation. where rotateRev(front, middle, rear)

2623-482: The lazy part of the implementation, this would be a non-persistent implementation of queue in O (1) amortized time . In this case, the lists tail_front and tail_rear could be removed from the representation of the double-ended queue. Ada 's containers provides the generic packages Ada.Containers.Vectors and Ada.Containers.Doubly_Linked_Lists , for the dynamic array and linked list implementations, respectively. C++'s Standard Template Library provides

2684-404: The lengths of either input or output and therefore runs in constant time. However the dequeue operation is more complicated. If the output array already has some elements in it, then dequeue runs in constant time; otherwise, dequeue takes ⁠ O ( n ) {\displaystyle O(n)} ⁠ time to add all the elements onto the output array from the input array, where n

2745-958: The library to exist on the same machine, but can forward the requests over the network. However, such an approach means that every library call requires a considerable amount of overhead. RPC calls are much more expensive than calling a shared library that has already been loaded on the same machine. This approach is commonly used in a distributed architecture that makes heavy use of such remote calls, notably client-server systems and application servers such as Enterprise JavaBeans . Code generation libraries are high-level APIs that can generate or transform byte code for Java . They are used by aspect-oriented programming , some data access frameworks, and for testing to generate dynamic proxy objects. They also are used to intercept field access. The system stores libfoo.a and libfoo.so files in directories such as /lib , /usr/lib or /usr/local/lib . The filenames always start with lib , and end with

2806-457: The library's required files and metadata. For example, a framework called MyFramework would be implemented in a bundle called MyFramework.framework , with MyFramework.framework/MyFramework being either the dynamically linked library file or being a symlink to the dynamically linked library file in MyFramework.framework/Versions/Current/MyFramework . Dynamic-link libraries usually have

2867-501: The majority of the system services. Such libraries have organized the services which a modern application requires. As such, most code used by modern applications is provided in these system libraries. The idea of a computer library dates back to the first computers created by Charles Babbage . An 1888 paper on his Analytical Engine suggested that computer operations could be punched on separate cards from numerical input. If these operation punch cards were saved for reuse then "by degrees

2928-521: The mid 1960s, copy and macro libraries for assemblers were common. Starting with the popularity of the IBM System/360 , libraries containing other types of text elements, e.g., system parameters, also became common. In IBM's OS/360 and its successors this is called a partitioned data set . The first object-oriented programming language, Simula , developed in 1965, supported adding classes to libraries via its compiler. Libraries are important in

2989-488: The modules required by a program are sometimes statically linked and copied into the executable file. This process, and the resulting stand-alone file, is known as a static build of the program. A static build may not need any further relocation if virtual memory is used and no address space layout randomization is desired. A shared library or shared object is a file that is intended to be shared by executable files and further shared object files . Modules used by

3050-472: The names and entry points of the code located within, they also require a list of the objects they depend on. This is a side-effect of one of OOP's core concepts, inheritance, which means that parts of the complete definition of any method may be in different places. This is more than simply listing that one library requires the services of another: in a true OOP system, the libraries themselves may not be known at compile time , and vary from system to system. At

3111-440: The order of elements. The basic operations on a deque are enqueue and dequeue on either end. Also generally implemented are peek operations, which return the value at that end without dequeuing it. Names vary between languages; major implementations include: There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly linked list . The dynamic array approach uses

SECTION 50

#1732855329913

3172-449: The persistency is not used; but the worst-time complexity of an operation is O ( n ) where n is the number of elements in the double-ended queue. Let us recall that, for a list l , |l| denotes its length, that NIL represents an empty list and CONS(h, t) represents the list whose head is h and whose tail is t . The functions drop(i, l) and take(i, l) return the list l without its first i elements, and

3233-430: The program linking or binding process, which resolves references known as links or symbols to library modules. The linking process is usually automatically done by a linker or binder program that searches a set of libraries and other modules in a given order. Usually it is not considered an error if a link target can be found multiple times in a given set of libraries. Linking may be done when an executable file

3294-483: The queue abstract data type or first in first out list ( FIFO ), where elements can only be added to one end and removed from the other. This general data class has some possible sub-types: Both the basic and most common list types in computing, queues and stacks can be considered specializations of deques, and can be implemented using deques. A deque is a data structure that allows users to perform push and pop operations at both ends, providing flexibility in managing

3355-433: The rear of the queue, of length len_rear . Furthermore, it is assured that |front| ≤ 2|rear|+1 and |rear| ≤ 2|front|+1 - intuitively, it means that both the front and the rear contains between a third minus one and two thirds plus one of the elements. Finally, tail_front and tail_rear are tails of front and of rear , they allow scheduling the moment where some lazy operations are forced. Note that, when

3416-424: The rough OOP equivalent of older types of code libraries. They contain classes , which describe characteristics and define actions ( methods ) that involve objects. Class libraries are used to create instances , or objects with their characteristics set to specific values. In some OOP languages, like Java , the distinction is clear, with the classes often contained in library files (like Java's JAR file format ) and

3477-424: The same time many developers worked on the idea of multi-tier programs, in which a "display" running on a desktop computer would use the services of a mainframe or minicomputer for data storage or processing. For instance, a program on a GUI-based computer would send messages to a minicomputer to return small samples of a huge dataset for display. Remote procedure calls (RPC) already handled these tasks, but there

3538-528: The status of the "next big thing" in the programming world. There were a number of efforts to create systems that would run across platforms, and companies competed to try to get developers locked into their own system. Examples include IBM 's System Object Model (SOM/DSOM), Sun Microsystems ' Distributed Objects Everywhere (DOE), NeXT 's Portable Distributed Objects (PDO), Digital 's ObjectBroker , Microsoft's Component Object Model (COM/DCOM), and any number of CORBA -based systems. Class libraries are

3599-521: The subroutine library for this computer. Programs for EDSAC consisted of a main program and a sequence of subroutines copied from the subroutine library. In 1951 the team published the first textbook on programming, The Preparation of Programs for an Electronic Digital Computer , which detailed the creation and the purpose of the library. COBOL included "primitive capabilities for a library system" in 1959, but Jean Sammet described them as "inadequate library facilities" in retrospect. JOVIAL has

3660-475: The suffix *.DLL , although other file name extensions may identify specific-purpose dynamically linked libraries, e.g. *.OCX for OLE libraries. The interface revisions are either encoded in the file names, or abstracted away using COM-object interfaces. Depending on how they are compiled, *.LIB files can be either static libraries or representations of dynamically linkable libraries needed only during compilation, known as " import libraries ". Unlike in

3721-467: Was no standard RPC system. Soon the majority of the minicomputer and mainframe vendors instigated projects to combine the two, producing an OOP library format that could be used anywhere. Such systems were known as object libraries , or distributed objects , if they supported remote access (not all did). Microsoft's COM is an example of such a system for local use. DCOM, a modified version of COM, supports remote access. For some time object libraries held

SECTION 60

#1732855329913
#912087