ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

-base cases
fibonacci(0)=0
fibonacci(1)=1

-recursive case
fibonacci(n) = fibonacci(n-1)+fibonacci(n-2)
n > 1

A procedure, fibonacci, that takes a natural number as its input, and returns the value of that fibonacci number.

def fibonacci(n):
    if n == 0:
      return 0
    if n == 1:
      return n
    return fibonacci(n-1) + fibonacci(n-2)

fibonacci has interesting feature below
fibo(x) = fibo(x-n-1)

More faster fibonacci procedure using for loop.

def fibonacci(n):
    current = 0
    after = 1
    for i in range(0, n):
      current, after = after, current + after
    return current

mass_of_earth = 5.9722 * 10**24
mass_of_rabbit = 2

n = 1
while fibonacci(n) * mass_of_rabbit < mass_of_earth:
  n = n + 1
print n, fibonacci(n)

- Ranking web pages as popularity
popularity(p) = # of people who are friends with p
popularity(p) = Σ popularity(f), f E friends of p

def popularity(p):
score = 0
for f in friends(p):
score = score + popularity(f)
return score

factorial(n) = n*(n-1)*(n-2)*…1

factorial(n)=1
factorial(n)=n*factorial(n-1)

A procedure, factorial, that takes a natural number as its input, and returns the number of ways to arrange the input number of items.

def factorial(n):
 if n == 0:
   return 1
 else:
   return n * factorial(n-1)

Palindromes:match the first and last string, such as level.
A procedure is_palindrome, that takes as input a string, and returns a Boolean indicating if the input string is a palindrome.

def is_palindrome(s):
  if s == "":
    return True
  else:
    if s[1] == s[-1]:
        return is_palindrome(s[1:-1])
    else:
        return false

Another way, using for loop, to write palindrome procedure.

def iter_palindrome(s):
  for i in range(0, len(s)/2):
    if s[i] != s[-(i + 1)]:
      return False
  return True

String: sequence of characters, immutable
ex. ‘hello’, s[i] is i th character in S
List: list of elements, mutable
ex. [‘alpha’, 23], p[i] is i th element of p
Dictionary: set of pairs, mutable
ex. {‘hydrogen’: 1, ‘helium’: 23, d[k], k is whatever the key value
ex. d[k] = v, is similar to the update.

Here is a example to use dictionary

elements = {'hydrogen':1, 'helium':2, 'carbon':6 }
elements['lithimu'] = 3
elements['nitrogen'] = 8
elements['nitrogen'] = 7
print elements['nitrogen']

population = {'Shanghai':17.8, 'Istanbul':13.3, 'Karachi':13.0, 'Mumbai':12.5 }

another example

elements = {}
elements['H'] = {'name': 'Hydrogen', 'number': 1, 'weight': 1.00794}
elements['He'] = {'name': 'Helium', 'number': 2, 'weight': 4.002602, 'noble gas': True}
print elements['He']['name']

procedure return a list of strings that break the source string up by the characters in the splitlist.

def split_string(source,splitlist):
  output = []
  atsplit = True
  for char in source:
    if char in splitlist:
      atsplit = True:
    else:
      if atsplit:
        output.append(char)
        atsplit = False
      else:
        output[-1] = output[-1] + char
    return output

cut duplicated url on index list

def add_to_index(index, keyword, url):
    for entry in index:
        if entry[0] == keyword:
            if not url in entry[1]:
            entry[1].append(url)
            return
    # not found, add new keyword to index
    index.append([keyword, [url]])

One way search engines rank pages is to count the number of times a searcher clicks on a returned link. This indicates that the person doing the query thought this was a useful link for the query, so it should be higher in the rankings next time.

def record_user_click(index,keyword,url):
  urls = lookup(index, keyword)
  if urls:
    for entry in urls:
      if entry[0] == url:
        entry[1] = entry[1] + 1
      
def add_to_index(index,keyword,url):
  for entry in index:
    for entry[0] == keyword:
      for elment in entry[1]:
        if element[0] = url:
          return
      entry[1].append([url,0])
      return
  index.append([keyword,[[url,0]]])

How program run fast making things fast. It depends algorithm analysis that most programmer spend time in procedure, well defined sequence of steps that can be executed mechanically. So gatta think about time and memory said cost of computer.

time consuming

import time

def time_execution(code):
  start = time.clock()
  result = eval(code)
  run_time = time.clock() - start
  return result, run_time

def spin_loop(n):
  i = 0
  while i < n:
    i = i + 1
    
print time_execution('2 ** 10')


Python 2.7.10 (default, Jul 14 2015, 19:46:27)
[GCC 4.8.2] on linux
(1024, 1.6000000000002124e-05)

print time_execution('spin_loop(10000000)')
(None, 0.33208099999999996)

Creating an Empty Hash Table, make_hashtable, that takes as input a number, nbuckets, and returns an empty hash table with nbuckets empty buckets.

def make_hashtable(nbuckets):
  i = 0
  table = []
  while i < nbuckets:
    table.append([])
    i = i + 1
  return table

for loop, we do not need variable like i.

def make_hashtable(nbuckets):
  i = 0
  table = []
  for unused < range(0, nbuckets):
    tabale.append([])
  return table

Update hashtable, if key is already in the table, change the value to the new value.

def hashtable_update(htable,key,value):
    bucket = hashtable_get_bucket(htable, key)
    for entry in hashtable
        if entry[0] == key:
          entry[1] = value
    bucket.append([key, value])