You will be an engineer in 100 days ――Day 61 ――Programming ――About exploration

Click here until yesterday

You will become an engineer in 100 days-Day 59-Programming-Algorithms

You will become an engineer in 100 days --- Day 53 --Git --About Git

You will become an engineer in 100 days --Day 42 --Cloud --About cloud services

You will become an engineer in 100 days --Day 36 --Database --About the database

You will be an engineer in 100 days --Day 24 --Python --Basics of Python language 1

You will become an engineer in 100 days --Day 18 --Javascript --JavaScript basics 1

You will become an engineer in 100 days --Day 14 --CSS --CSS Basics 1

You will become an engineer in 100 days --Day 6 --HTML --HTML basics 1

About exploration

Search in programming is to find the desired data.

There are various forms of data and how to search for data.

Linear search

When data is stored in list, in order from the beginning of the list If you look to the end of the list, you will find the data you want.

Such a search method is called linear search. It's simple and easy to implement because you only need to check in order.

The following example is a simple linear search example.

data = [6342, 4588, 2362, 6812, 6102, 5119, 2631, 3548, 4559, 3570]
target = 4559
flg = False

##Example of linear search
def linear_search(data, val):
    for x in data:
        if x == val:
            return True
    return False

print(linear_search(data, target))

True

I think it's a relatively easy-to-understand algorithm It will be difficult if there is more data that needs to be examined until all the values are found.

I'm looking for numbers in order from the top of the list, but if it's at the back of the list It will take a long time.

Average number of comparisons for $ \ frac {n + 1} {2} $ In the worst case, it will be $ O (n) $ processing.

Binary search

Considering how to find out quickly even if the number of data increases in the list Linear search is difficult.

When you look at a certain value, such as a dictionary or phone book, the desired value is higher than that. As a way to judge whether it is big or small A method to search at high speed by repeating the operation of narrowing down the search range to half It is called binary search.

#Binary search example
def binary_search(data, num):
    left , right = 0 , len(data) - 1
    while left <= right:
        m = (left + right) // 2
        if data[m] == num:
            return m
        elif data[m] < num:
            left = m + 1
        else:
            right = m - 1
    return -1

data = [6342, 4588, 2362, 6812, 6102, 5119, 2631, 3548, 4559, 3570]
data.sort()
print(data)
print(binary_search(data, 5119))

The data must be sorted to allow binary search. Sort the data before searching.

Breadth search

Not when searching for data stored in a list Suppose you want to find the desired data in the data that has a hierarchical structure.

For example, from data with a tree-like structure such as a website When finding the desired page At that time, breadth-first search and depth-first search can be considered.

Breadth first search

How to list things close to where you start your search and scrutinize each one It is called breadth-first search (BFS).

# BFS(Breadth-first search)
import os
from collections import deque
 
def bfs(path):
    q = deque([])
    q.append(path)
    while len(q) > 0:
        p = q.popleft()
        print (p)
        for child in os.listdir(p):
            child_path = p + '/' + child
            if os.path.isdir(child_path):
                q.append(child_path)
    return q

print(bfs('./'))

Depth first search

For breadth-first search, how to proceed as far as you want and return when you can't. It is called depth-first search (DFS).

Also known as the backtrack method.

import os
from collections import deque
 
def dfs(path):
    q = deque([]) 
    q.append(path)
    while len(q) > 0:
        p = q.pop()
        print (p)
        for child in os.listdir(p):
            child_path = p + '/' + child
            if os.path.isdir(child_path):
                q.append(child_path) 
    return q

print(dfs('./'))

Summary

A wide variety of data search methods The amount of calculation and execution speed will change greatly depending on how to assemble and search the data.

With the optimum data format according to the data to be handled Consider the exploration algorithm.

39 days until you become an engineer

Author information

Otsu py's HP: http://www.otupy.net/

Youtube: https://www.youtube.com/channel/UCaT7xpeq8n1G_HcJKKSOXMw

Twitter: https://twitter.com/otupython

Recommended Posts

You will be an engineer in 100 days ――Day 61 ――Programming ――About exploration
You will be an engineer in 100 days ――Day 71 ――Programming ――About scraping 2
You will be an engineer in 100 days ――Day 74 ――Programming ――About scraping 5
You will be an engineer in 100 days ――Day 73 ――Programming ――About scraping 4
You will be an engineer in 100 days ――Day 75 ――Programming ――About scraping 6
You will be an engineer in 100 days --Day 68 --Programming --About TF-IDF
You will be an engineer in 100 days ――Day 70 ――Programming ――About scraping
You will be an engineer in 100 days ――Day 81 ――Programming ――About machine learning 6
You will be an engineer in 100 days ――Day 82 ――Programming ――About machine learning 7
You will be an engineer in 100 days ――Day 79 ――Programming ――About machine learning 4
You will be an engineer in 100 days ――Day 76 ――Programming ――About machine learning
You will be an engineer in 100 days ――Day 80 ――Programming ――About machine learning 5
You will be an engineer in 100 days ――Day 78 ――Programming ――About machine learning 3
You will be an engineer in 100 days ――Day 84 ――Programming ――About machine learning 9
You will be an engineer in 100 days ――Day 83 ――Programming ――About machine learning 8
You will be an engineer in 100 days ――Day 77 ――Programming ――About machine learning 2
You will be an engineer in 100 days ――Day 85 ――Programming ――About machine learning 10
You will be an engineer in 100 days --Day 63 --Programming --Probability 1
You will be an engineer in 100 days --Day 65 --Programming --Probability 3
You will be an engineer in 100 days --Day 64 --Programming --Probability 2
You will be an engineer in 100 days --Day 86 --Database --About Hadoop
You will be an engineer in 100 days ――Day 60 ――Programming ――About data structure and sorting algorithm
You will be an engineer in 100 days --Day 27 --Python --Python Exercise 1
You will be an engineer in 100 days --Day 34 --Python --Python Exercise 3
You will be an engineer in 100 days --Day 31 --Python --Python Exercise 2
You become an engineer in 100 days ――Day 67 ――Programming ――About morphological analysis
You become an engineer in 100 days ――Day 66 ――Programming ――About natural language processing
You will be an engineer in 100 days ――Day 24 ―― Python ―― Basics of Python language 1
You will be an engineer in 100 days ――Day 30 ―― Python ―― Basics of Python language 6
You will be an engineer in 100 days ――Day 25 ―― Python ―― Basics of Python language 2
You will be an engineer in 100 days --Day 29 --Python --Basics of the Python language 5
You will be an engineer in 100 days --Day 33 --Python --Basics of the Python language 8
You will be an engineer in 100 days --Day 26 --Python --Basics of the Python language 3
You will be an engineer in 100 days --Day 35 --Python --What you can do with Python
You will be an engineer in 100 days --Day 32 --Python --Basics of the Python language 7
You will be an engineer in 100 days --Day 28 --Python --Basics of the Python language 4
You have to be careful about the commands you use every day in the production environment.
What beginners think about programming in 2016