Karteikarten
PREP
Karten in diesem Stapel (22)
- 1Memory Management - C#C# is a strongly typed object-oriented language created at Microsoft in 1999–2000. It is designed to run on the Common Language Runtime, the virtual machine from the .NET Framework. It also runs on the open source Mono runtime.
Memory is automatically managed: memory is allocated when an object is created, and reclaimed at some point after the object becomes unreachable.
The language supports finalization (classes may have destructor functions, which are run just before the object is reclaimed by the memory manager), and weak references(1) (via the WeakReference class).
The garbage collector in the .NET Framework is configurable to run in soft real time, or in batch mode.
The Mono runtime comes with two collectors: the Boehm–Demers–Weiser conservative collector, and a generational copying collector. - 2Memory Management - C++C++ is a (weakly) object-oriented language, extending the systems programming language C with a multiple-inheritance class mechanism and simple method dispatch.
The standard library functions for memory(2) management in C++ are new and delete. The higher abstraction level of C++ makes the bookkeeping required for manual memory management even harder. Although the standard library provides only manual memory management, with the Memory Pool System, or the Boehm–Demers–Weiser collector, it is now possible to use garbage collection. Smart pointers are another popular solution.
The language is notorious for fostering memory management bugs, including:
Using stack-allocated structures beyond their lifetimes (see use after free);
Using heap-allocated structures after freeing them (see use after free);
Neglecting to free heap-allocated objects when they are no longer required (see memory leak);
Excessive copying by copy constructors(1);
Unexpected sharing due to insufficient copying by copy constructors;
Allocating insufficient memory for the intended contents;
Accessing arrays with indexes that are out of bounds. - 3Memory Management - JavaA modern object-oriented language with a rich collection of useful features. The Java language started as an attempt by the Java group at Sun Microsystems to overcome software engineering problems introduced by C++. Key reasons for the language’s success were the security model and the portable execution environment, the Java Virtual Machine (JVM), which created a lot of interest for it as a platform for distributed computing on open networks.
Java is garbage-collected, as this facilitates object-oriented programming and is essential for security (which use after free would break). It had finalization from version 1.0 and three kinds of weakness from version 1.2 (confusingly, part of the Java 2 Platform).
Early JVMs had simple collectors that didn’t scale well for large programs, but the current crop is catching up to the state of the art. - 4Memory Managment - JavscriptJavaScript is a scripting language used by web browsers. The loose type system resembles other scripting languages, although the syntax follows C. There’s a prototype-based object system. Note that JavaScript is not related to Java in any way except name. There’s a standard by ECMA, known as ECMAScript.
Despite the C++-like syntax (with new and delete operators), JavaScript is garbage-collected - 5Regular Expression BasicsSpecial Characters \ ^ $ . | ? * + ( ) [ {
Character Class [ae] gray grey
[0-9] Single digit between 0-9
[0-9a-fA-F] hexadecimal range
q[^x] Not character x
dot matches any character - use sparingly, might be slower than character
^ is start of string $ is end of string
(cat|dog) food - Alternation
\1 for backreference - 6TradesoffsI think you already have a good grasp of the issues. It really is a trade off between efficiency and safety.
C today is what assembly language was 10 or 15 years ago. It's the language you use when efficiency or low level access to hardware really matters to you. You can, of course, still use assembly language today. But optimizing C/C++ compilers are so good today, that they can often trump hand coded assembly language.
So...C is very fast, and very good for low level, hardware level access. Do you need those features? Let's assume you aren't writing device drivers, so you don't need hardware access. It's all about speed.
Java (and other modern, safe languages like C#) are slower than C.
Take a very simple example. You have an array and you are putting stuff in it based on an index variable you calculate at run time.
ary[x] = 1;
Java looks at the value of x and makes sure that it is a valid index for ary. If it is, it will store 1 at the right memory location for you. If it isn't, it throws an exception.
C takes the value of x, multiplies it by the size of whatever ary is, and stores the value 1 at that memory location.
Java (and C# et. el. ) are slower because they make that extra test to be sure that x is valid.
So C is better, right? It does the same thing faster.
Yes...It's better if your code is 100% bug free and you always calculate a valid value for x.
But what if...GASP!!! YOU HAVE BUGS? Now, your code doesn't have any bugs in it, right? Most of us do write perfect code that never has any bugs. That's the norm.
But, just for kicks...assume you do have a bug. You calculate -1 for x. or 4 Billion.
Java will stop you dead in your tracks. With a stack trace that tells you how you got to your bug. You might hate seeing it, but there it is....you have a bug.
What will C do? It will write a value to a memory address. If you are lucky, that might seg-fault on you, and at least it slaps you in the face the same way Java did (but probably without the stack trace). Or, often times, you aren't lucky. You just spray data in random places in memory. Eventually, that will probably lead to strange, weird, impossible to reproduce bugs that you can (and I mean this literally) spend months trying to track down. BTDT.
Computers have gotten amazingly fast in the last decade. How often does faster really matter anymore? Certainly, sometimes it does. Leading edge games often need every CPU cycle they can get. Programs that crunch massive amounts of data need every CPU cycle they can get. If I click a button in your JAVA UI, and it takes you 10 milliseconds to process it instead of the 5 milliseconds that C might take...will I care? No. It's imperceptible.
So...C....Fast. do you need fast? Or is time to market more important? You will finish your code faster, and the code will be more robust if you use a high level language like Java or C#.
It is an engineering trade-off. Speed. Safety. Time to market. Support costs. Developer productivity. You have to weigh all those things and make the right choice. (And many programmers seem to be obsessed with the speed thing...even when it really doesn't matter). - 7Tradesoffs ContinuedPros of C++:
Potentially better performance of CPU-bound code (if you know how to write it).
Direct access to the underlying system libraries.
Ability to control memory layout.
Ability to fine-tune performance for specific architectures.
Ability to use the RAII pattern, thanks to eager invocation of destructors at scope boundaries.
More predictable (i.e., lower variance) latency, since there's no garbage collector throwing random pauses in.
The much-maligned preprocessor, which can actually be very useful for implementing certain idioms, especially crosscutting concerns like logging.
Pros of Java:
Write once, run anywhere: you can test your code on your OS X laptop and run it without change on a production Linux machine.
Stability: if you handle exceptions properly, a single misbehaving thread usually can't crash the entire server process.
Easier to write: No need to worry about memory management (not that this is as difficult as people sometimes make it out to be)
Great tool support: IDEs etc.
Regular introduction of new versions with new language features.
An explicit memory model (although C++0x now has one too)
More convenient syntax for iteration (again, C++0x now has this too) - 8Tradeoffs revisitedA "performance matrix" is a comparison of certain metrics (like use of memory, use of CPU, time required to execute, time required to code) in executing a given algorithm when coded in different way.
The "production process" for C++ C# and Java are different, as the constructs an coding paradigm they rely on, and in the libraries providing the basic functionalities.
In particular,
C++ is [code -> compile] -> execute,
C# is [code -> precompile] -> [compile -> execute]
Java is [code -> precompile] -> [parse]
But:
C++ requires manual resource management (faster but more complex to code)
C# and Java use garbage collection (slower, but easier to code).
C# is slower in start that java (require a just-in-time compilation) but faster in bare execution (is executed as machine code)
And:
C++ is based on C that is the native language of the Windows API (and of many hardware dependent specific code)
C# is the native language of the .Net platform
Java works on a virtual machine that exist for a wide variety of platforms. - 9ArrayComputed at run time
Used to impliment other data structures
2 dimenstions = matrices
Can also direct path of execution (multiple if and switch)
The simplest type of data structure is a linear array - 10Linked ListIn computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.
The principal benefit of a linked list over a conventional array is that the list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk
Advantages:
Linked lists are a dynamic data structure, allocating the needed memory when the program is initiated.
Insertion and deletion node operations are easily implemented in a linked list.
Linear data structures such as stacks and queues are easily executed with a linked list.
They can reduce access time and may expand in real time without memory overhead.
Disadvantages:
They have a tendency to waste memory due to pointers requiring extra storage space.
Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list.
Difficulties arise in linked lists when it comes to reverse traversing. Singly linked lists are extremely difficult to navigate backwards, and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back pointer. - 11TreeCommon Uses: Representing hierarchical data
Storing data in a way that makes it easily searchable (see binary search tree and tree traversal)
Representing sorted lists of data
As a workflow for compositing digital images for visual effects
Routing algorithms
Common Operations:
Enumerating all the items
Enumerating a section of a tree
Searching for an item
Adding a new item at a certain position on the tree
Deleting an item
Pruning: Removing a whole section of a tree
Grafting: Adding a whole section to a tree
Finding the root for any node
A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root. - 12HeapIn computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. Either the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node (this kind of heap is called max heap) or the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node (min heap). Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree (see figure).
Applications
The heap data structure has many applications.
Heapsort: One of the best sorting methods being in-place and with no quadratic worst-case scenarios.
Selection algorithms: A heap allows access to the min or max element in constant time, and other selections (such as median or kth-element) can be done in sub-linear time on data that is in a heap.[8]
Graph algorithms: By using heaps as internal traversal data structures, run time will be reduced by polynomial order. Examples of such problems are Prim's minimal-spanning-tree algorithm and Dijkstra's shortest-path algorithm.
Priority Queue: A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods.
Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array. - 13hashIn computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.
Ideally, the hash function will assign each key to a unique bucket, but this situation is rarely achievable in practice (usually some keys will hash to the same bucket). Instead, most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur and must be accommodated in some way.
--
Hash tables are commonly used to implement many types of in-memory tables. They are used to implement associative arrays (arrays whose indices are arbitrary strings or other complicated objects), especially in interpreted programming languages like AWK, Perl, and PHP.
Database indexing - 14StackIn computer science, a stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection, known as push and removal of an entity, known as pop.[1] The relation between the push and pop operations is such that the stack is a Last-In-First-Out (LIFO) data structure. In a LIFO data structure, the last element added to the structure must be the first one to be removed. This is equivalent to the requirement that, considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack. Often a peek or top operation is also implemented, returning the value of the top element without removing it.
A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed, the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack. A pop either reveals previously concealed items or results in an empty stack, but, if the stack is empty, it goes into underflow state, which means no items are present in stack to be removed.
A stack is a restricted data structure, because only a small number of operations are performed on it. The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition. Therefore, the lower elements are those that have been on the stack the longest.[2]
Stacks have numerous applications. We see stacks in everyday life, from the books in our library, to the blank sheets of paper in our printer tray. All of them follow the Last In First Out (LIFO) logic, that is when we add a book to a pile of books, we add it to the top of the pile, whereas when we remove a book from the pile, we generally remove it from the top of the pile.
Given below are a few applications of stacks in the world of computers:
Converting a decimal number into a binary number[edit]
Decimal to binary conversion of 23
The logic for transforming a decimal number into a binary number is as follows:
Read a number
Iteration (while number is greater than zero)
Find out the remainder after dividing the number by 2
Print the remainder
End the iteration
However, there is a problem with this logic. Suppose the number, whose binary form we want to find, is 23. Using this logic, we get the result as 11101, instead of getting 10111.
To solve this problem, we use a stack.[7] We make use of the LIFO property of the stack. Initially we push the binary digit formed into the stack, instead of printing it directly. After the entire number has been converted into the binary form, we pop one digit at a time from the stack and print it. Therefore we get the decimal number converted into its proper binary form. - 15QueueIn computer science, a queue (/ˈkjuː/ kew) is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Often a peek or front operation is also entered, returning the value of the front element without dequeuing it. A queue is an example of a linear data structure, or more abstractly a sequential collection.
Queues provide services in computer science, transport, and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the queue performs the function of a buffer.
Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes. Common implementations are circular buffers and linked lists. - 16TrieIn computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.
The term trie comes from retrieval. This term was coined by Edward Fredkin, who pronounces it /ˈtriː/ "tree" as in the word retrieval.[1][2] However, other authors pronounce it /ˈtraɪ/ "try", in an attempt to distinguish it verbally from "tree".[1][2][3]
In the example shown, keys are listed in the nodes and values below them. Each complete English word has an arbitrary integer value associated with it. A trie can be seen as a deterministic finite automaton without loops. Each finite language is generated by a trie automaton, and each trie can be compressed into a DAFSA.
It is not necessary for keys to be explicitly stored in nodes. (In the figure, words are shown only to illustrate how the trie works.)
Though tries are most commonly keyed by character strings, they don't need to be. The same algorithms can easily be adapted to serve similar functions of ordered lists of any construct, e.g., permutations on a list of digits or shapes. In particular, a bitwise trie is keyed on the individual bits making up a short, fixed size of bits such as an integer number or memory address. - 17GraphIn computer science, a graph is an abstract data type that is meant to implement the graph and hypergraph concepts from mathematics.
A graph data structure consists of a finite (and possibly mutable) set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices. As in mathematics, an edge (x,y) is said to point or go from x to y. The nodes may be part of the graph structure, or may be external entities represented by integer indices or references.
A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).
Different data structures for the representation of graphs are used in practice:
Adjacency list
Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices.
Adjacency matrix
A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.
Incidence matrix
A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column.
The following table gives the time complexity cost of performing various operations on graphs, for each of these representations.[citation needed] In the matrix representations, the entries encode the cost of following an edge. The cost of edges that are not present are assumed to be \infty . - 18Bubble SortBubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.
/ Bubble Sort Function for Descending Order
void BubbleSort(apvector &num)
{
int i, j, flag = 1; // set flag to 1 to start first pass
int temp; // holding variable
int numLength = num.length( );
for(i = 1; (i <= numLength) && flag; i++)
{
flag = 0;
for (j=0; j < (numLength -1); j++)
{
if (num[j+1] > num[j]) // ascending order simply changes to <
{
temp = num[j]; // swap elements
num[j] = num[j+1];
num[j+1] = temp;
flag = 1; // indicates that a swap occurred.
}
}
}
return; //arrays are passed to functions by address; nothing is returned
}
less than a thousand - 19Merge SortThe merge sort combines two sorted arrays into
one larger sorted array.
As the diagram at the left shows,
Array A and Array B merge to form Array C.
Arrays to be merged MUST be SORTED FIRST!!
Be sure to declare Array C in main( ) and establish its size.
Although heapsort has the same time bounds as merge sort, it requires only Θ(1) auxiliary space instead of merge sort's Θ(n). On typical modern architectures, efficient quicksort implementations generally outperform mergesort for sorting RAM-based arrays.[citation needed] On the other hand, merge sort is a stable sort and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible - 20Quick sortThe quicksort is considered to be very efficient, with its "divide and conquer" algorithm. This sort starts by dividing the original array into two sections (partitions) based upon the value of the first element in the array. Since our example sorts into descending order, the first section will contain all the elements greater than the first element. The second section will contain elements less than (or equal to) the first element. It is possible for the first element to end up in either section.
Let's examine our same example: - 21Depth FirstDepth – first searches are performed by diving downward into a tree as quickly as possible. It does this by always generating a child node from the most recently expanded node, then generating that child’s children, and so on until a goal is found or some cutoff depth point d is reached. If a goal is not found when a leaf node is reached or at the cutoff point, the program backtracks to the most recently expanded node and generates another of its children. This process continues until a goal is found or failure occurs.
- 22Breadth First searchBreadth – first searches are performed by exploring all nodes at a given depth before proceeding to the next level. This means that all immediate children of nodes are explored before any of the children’s children are considered. It has obvious advantage of always finding a minimal path length solution when one exists. However, a great many nodes may need to be explored before a solution is found, especially if the tree is very full.
Informationen
- Beschreibung
- Karteikarten am PREP, erstellt von william.carswell am 04/07/2014.
- Erstellt von
- william.carswell
- Aufrufe
- 37
- Bewertung