R Data Structures and Algorithms by Dr. PKS Prakash & Achyutuni Sri Krishna Rao

Author:Dr. PKS Prakash & Achyutuni Sri Krishna Rao [Prakash, Dr. PKS]
Language: eng
Format: azw3, pdf
Publisher: Packt Publishing
Published: 2016-11-20T16:00:00+00:00

The approaches discussed in the first two sections are more effective in implementation while using an in-memory-(single node) based system, and the third approach discussed is more effective in implementation while using either in-memory-(single node) or disks (multiple nodes) based systems.

Searching unsorted and sorted vectors

Vectors are simple and widely used data structures used to perform search operations in R. The simplest form of search operation performed on vectors is a linear search or sequential search. In a linear search, each element is compared sequentially within the vector, and then suitable insertions or deletions are performed. Consider an element, S which is to be searched in an unsorted vector, V of length n (indexed from 1 to n). If the element S is not present in vector V, then a minimum of n comparisons are performed, and if it is present in V at position i, then a minimum of i comparisons are performed. In both scenarios, the number of comparisons is linear, resulting in O(n) as the functional form of system runtime for sequential search in the worst case scenario. The following R code performs a linear search of element S in a vector V of length n:

Sequential_search <- function(V,S,n) { i=1 present = FALSE while(i <= n & present==FALSE) { if(V[i] == S) present=TRUE else i = i+1 } return(list(present=present,key=i)) }

Figure 6.1 illustrates two different sequential operations. Part (a) represents the situation wherein the element S is not present, and Part (b) represents the presence of element S. Each step corresponds to a comparison, regardless of whether the current element in the vector is equal to S or not:

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.