Python - Searching and Sorting - linear search, while loop, for loop, sentinel, TDD(test-driven development)

Practical Programming
楽天ブックス 紀伊国屋書店

開発環境

• macOS Catalina - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.8 (プログラミング言語)

Practical Programming: An Introduction to Computer Science Using Python 3.6 (Paul Gries(著)、Jennifer Campbell(著)、Jason Montojo(著)、Pragmatic Bookshelf)のChapter 13(Searching and Sorting)、Exercise 1の解答を求めてみる。

コード

#!/usr/bin/env python3
from unittest import TestCase, main
from typing import Any

print('1.')


class TestLinearSearch(TestCase):
    def test1(self):
        self.assertEqual(linear_search([2, 5, 1, -3], 5), 1)

    def test0(self):
        self.assertEqual(linear_search([2, 4, 2], 2), 2)

    def test_none1(self):
        self.assertEqual(linear_search([2, 5, 1, -3], 4), -1)

    def test_empty(self):
        self.assertEqual(linear_search([], 5), -1)


def linear_search(lst: list, value: Any) -> int:
    i: int = len(lst) - 1
    while i >= 0 and lst[i] != value:
        i -= 1
    if i < 0:
        return -1
    return i


class TestLinearSearchForLoop(TestCase):
    def test1(self):
        self.assertEqual(linear_search_for_loop([2, 5, 1, -3], 5), 1)

    def test0(self):
        self.assertEqual(linear_search_for_loop([2, 4, 2], 2), 2)

    def test_none1(self):
        self.assertEqual(linear_search_for_loop([2, 5, 1, -3], 4), -1)

    def test_empty(self):
        self.assertEqual(linear_search_for_loop([], 5), -1)


def linear_search_for_loop(lst: list, value: Any) -> int:
    for i in range(len(lst) - 1, -1, -1):
        if lst[i] == value:
            return i
    return -1


class TestLinearSearchSentinel(TestCase):
    def test1(self):
        self.assertEqual(linear_search_sentinel([2, 5, 1, -3], 5), 1)

    def test0(self):
        self.assertEqual(linear_search_sentinel([2, 4, 2], 2), 2)

    def test_none1(self):
        self.assertEqual(linear_search_sentinel([2, 5, 1, -3], 4), -1)

    def test_empty(self):
        self.assertEqual(linear_search_sentinel([], 5), -1)


def linear_search_sentinel(lst: list, value: Any) -> int:
    lst.insert(0, value)
    i = len(lst) - 1
    while lst[i] != value:
        i -= 1
    lst.pop(0)
    if i == 0:
        return -1
    return i - 1


if __name__ == "__main__":
    main()

入出力結果(Zsh、PowerShell、Terminal、Jupyter(IPython))

% ./sample1.py 
1.
FFFF
======================================================================
FAIL: test0 (__main__.TestLinearSearch)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 13, in test0
    self.assertEqual(linear_search([2, 4, 2], 2), 2)
AssertionError: None != 2

======================================================================
FAIL: test1 (__main__.TestLinearSearch)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 10, in test1
    self.assertEqual(linear_search([2, 5, 1, -3], 5), 1)
AssertionError: None != 1

======================================================================
FAIL: test_empty (__main__.TestLinearSearch)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 19, in test_empty
    self.assertEqual(linear_search([], 5), -1)
AssertionError: None != -1

======================================================================
FAIL: test_none1 (__main__.TestLinearSearch)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 16, in test_none1
    self.assertEqual(linear_search([2, 5, 1, -3], 4), -1)
AssertionError: None != -1

----------------------------------------------------------------------
Ran 4 tests in 0.001s

FAILED (failures=4)
% ./sample1.py
1.
....
----------------------------------------------------------------------
Ran 4 tests in 0.000s

OK
% ./sample1.py 
1.
....FFFF
======================================================================
FAIL: test0 (__main__.TestLinearSearchForLoop)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 36, in test0
    self.assertEqual(linear_search_for_loop([2, 4, 2], 2), 2)
AssertionError: None != 2

======================================================================
FAIL: test1 (__main__.TestLinearSearchForLoop)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 33, in test1
    self.assertEqual(linear_search_for_loop([2, 5, 1, -3], 5), 1)
AssertionError: None != 1

======================================================================
FAIL: test_empty (__main__.TestLinearSearchForLoop)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 42, in test_empty
    self.assertEqual(linear_search_for_loop([], 5), -1)
AssertionError: None != -1

======================================================================
FAIL: test_none1 (__main__.TestLinearSearchForLoop)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 39, in test_none1
    self.assertEqual(linear_search_for_loop([2, 5, 1, -3], 4), -1)
AssertionError: None != -1

----------------------------------------------------------------------
Ran 8 tests in 0.001s

FAILED (failures=4)
% ./sample1.py 
1.
........
----------------------------------------------------------------------
Ran 8 tests in 0.000s

OK
% ./sample1.py 
1.
........FFFF
======================================================================
FAIL: test0 (__main__.TestLinearSearchSentinel)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 57, in test0
    self.assertEqual(linear_search_sentinel([2, 4, 2], 2), 2)
AssertionError: None != 2

======================================================================
FAIL: test1 (__main__.TestLinearSearchSentinel)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 54, in test1
    self.assertEqual(linear_search_sentinel([2, 5, 1, -3], 5), 1)
AssertionError: None != 1

======================================================================
FAIL: test_empty (__main__.TestLinearSearchSentinel)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 63, in test_empty
    self.assertEqual(linear_search_sentinel([], 5), -1)
AssertionError: None != -1

======================================================================
FAIL: test_none1 (__main__.TestLinearSearchSentinel)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "./sample1.py", line 60, in test_none1
    self.assertEqual(linear_search_sentinel([2, 5, 1, -3], 4), -1)
AssertionError: None != -1

----------------------------------------------------------------------
Ran 12 tests in 0.001s

FAILED (failures=4)
% open ../Exercise\ Solutions/Chapter13.pdf 
% ./sample1.py 
1.
............
----------------------------------------------------------------------
Ran 12 tests in 0.001s

OK
% ./sample1.py -v
1.
test0 (__main__.TestLinearSearch) ... ok
test1 (__main__.TestLinearSearch) ... ok
test_empty (__main__.TestLinearSearch) ... ok
test_none1 (__main__.TestLinearSearch) ... ok
test0 (__main__.TestLinearSearchForLoop) ... ok
test1 (__main__.TestLinearSearchForLoop) ... ok
test_empty (__main__.TestLinearSearchForLoop) ... ok
test_none1 (__main__.TestLinearSearchForLoop) ... ok
test0 (__main__.TestLinearSearchSentinel) ... ok
test1 (__main__.TestLinearSearchSentinel) ... ok
test_empty (__main__.TestLinearSearchSentinel) ... ok
test_none1 (__main__.TestLinearSearchSentinel) ... ok

----------------------------------------------------------------------
Ran 12 tests in 0.001s

OK
% mypy sample1.py 
Success: no issues found in 1 source file
%