Content deleted Content added
removed Category:Computer science; added Category:Software optimization using HotCat |
Typo/general fixes, replaced: the the → the, added orphan tag, typo(s) fixed: Often times → Oftentimes, a O → an O (2) using AWB |
||
Line 1:
{{Orphan|date=January 2016}}
In [[computer science]], '''input enhancement''' is the principle that processing a given input to a problem and altering it in a specific way will increase [[Time complexity|runtime efficiency]] or [[DSPACE|space efficiency]], or both. The altered input is usually stored and accessed to simplify the problem. By exploiting the structure and properties of the inputs, input enhancement creates various speed-ups in the efficiency of the [[algorithm]].
== Searching ==
Input enhancement when searching has been an essential component of the algorithm world for some time in computer science. The main idea behind this principle is that the efficiency of a search is much faster when the time is taken to create or sort a [[data structure]] of the given input before attempting to search for the element in said data structure.
=== Presorting ===
Line 18 ⟶ 20:
'''return true'''
Without a presort, at worst case, this algorithm would require every element to be checked against every other element with two possible outcomes: either there is no duplicate element in the array, or the last two elements in the array are the duplicates. This results in
Now compare this to a similar algorithm that utilizes presorting. This algorithm sorts the inputted array, and then checks each pair of elements for a duplicate. The pseudocode is presented below:
Line 29 ⟶ 31:
'''return true'''
As previously stated, the least efficient part of this algorithm is the sorting of the array, which, if an efficient sort is selected, would run in O(''n'' log ''n''). But after the array is sorted, the array only needs to be traversed once, which would run in O(''n''). This results in
This simple example demonstrates what is capable with an input enhancement technique such as presorting. The algorithm went from [[Time complexity
=== In Trees ===
Creating data structures to more efficiently search through data is also a form of input enhancement. Placing data into a tree to store and search through inputs is another popular technique. [[Tree (data structure)
The benefits of putting data in a tree are great, especially if the data is being manipulated or repeatedly searched through. Binary search trees are the most simplest, yet most common type of tree for this implementation. The insertion, deletion, and searching of items in a tree are all worst case O(''n''), but are most often executed in O(log ''n''). This makes the repeated searching of elements even quicker for large inputs. There are many different types of binary search trees that work more efficiently and even self-balance upon addition and removal of items, like the AVL tree which has a worst case O(log ''n'') for all searching, inserting, and deletion.
Taking the time to put the inputted data into such a structure will have great speed-ups for repeated searching of elements, as opposed to searching through the data that hasn't enhanced.
Line 65 ⟶ 67:
The fourth and last possible case is that character ''x'' matches the key but the other characters don’t fully match the key and ''x'' does occur again in the key. If this occurs, the key is shifted to align the rightmost occurrence if the character ''x''.
This may seem like it is not more efficient than the brute-force algorithm since it has to check all of the characters on every check. However, this is not the case. Horspool’s algorithm utilizes a shift table to store the number of characters the algorithm should shift if it runs into a specific character. The input is precomputed into a table with every possible character that can be encountered in the text. The shift size is computed with two options: one, if the character is in not in the key, then the shift size is ''n'', the length of the key; or two, if the character appears in the key, then its shift value is
'''algorithm''' shiftTableGenerator(K[0...''n''-1])
Line 103 ⟶ 105:
Input enhancement is often used interchangeably with [[precomputation]] and [[preprocessing]]. Although they are related, there are several important differences that must be noted.
*Precomputing and input enhancement can sometimes be used synonymously. More specifically, precomputation is the calculation of a given input before anything else is done to the input.
*When speaking about altering inputs, preprocessing is often misused. In computer science, a preprocessor and preprocessing are entirely different. When preprocessing is used in context, the usual intention is to portray the concept of input enhancement, and not that of utilizing a preprocessor. Implementing a preprocessor is the concept in which a program takes an input and processes it into an output to be used by another program entirely. This sounds like input enhancement, but the application of preprocessor applies to the generic program that processes the source input to be outputted in a format that a compiler can read and can then be compiled.
== References ==
* Levitin, Anany (2012). ''Introduction to The Design & Analysis of Algorithms'' (Third Edition). Pearson. ISBN 978-0-13-231681-1
* Sebesta, Robert W. (2012). ''Concepts of Programming Languages'' (Tenth Edition). Pearson. ISBN 978-0-13-139531-2
| |||