Thursday, January 3, 2019

Vasudev Ram: Multiple item search in an unsorted list in Python


- By Vasudev Ram - Online Python training / SQL training / Linux training



Hi, readers,

I was reviewing simple algorithms with a view to using some as examples or exercises in my Python programming course. While doing so, I thought of enhancing simple linear search for one item in a list, to make it search for multiple items.

Here are a couple of program versions I wrote for that task. They use straightforward logic. There are just a few additional points:

- In both programs, I use a generator to yield the values found (the index and the item).
- In the first program, I print out the index and item for each item found.
- In the second program, I mark where the items are found with text "arrows".

This is the first program, mult_item_search_unsorted_list.py:
# mult_item_search_unsorted_list.py 
# Purpose: To search for multiple items in an unsorted list.
# Prints each item found and its index.
# Author: Vasudev Ram
# Copyright 2019 Vasudev Ram
# Training: https://jugad2.blogspot.com/p/training.html
# Blog: https://jugad2.blogspot.com
# Web site: https://vasudevram.github.io
# Product store: https://gumroad.com/vasudevram

from __future__ import print_function
import sys
from random import sample, shuffle

def mult_item_search_unsorted_list(dlist, slist):
for didx, ditem in enumerate(dlist):
for sitem in slist:
if sitem == ditem:
yield (didx, ditem)

def main():
# Create the search list (slist) with some items that will be found
# and some that will not be found in the data list (dlist) below.
slist = sample(range(0, 10), 3) + sample(range(10, 20), 3)
# Create the data list.
dlist = range(10)
for i in range(3):
# Mix it up, DJ.
shuffle(slist)
# MIX it up, DEK.
shuffle(dlist)
print("\nSearching for:", slist)
print(" in:", dlist)
for didx, ditem in mult_item_search_unsorted_list(dlist, slist):
print(" found {} at index {}".format(ditem, didx))

main()
Output of a run:
$ python mult_item_search_unsorted_list.py

Searching for: [1, 18, 3, 15, 19, 4]
in: [8, 9, 1, 2, 0, 7, 5, 3, 6, 4]
found 1 at index 2
found 3 at index 7
found 4 at index 9

Searching for: [4, 19, 18, 15, 1, 3]
in: [7, 5, 8, 2, 9, 4, 0, 3, 6, 1]
found 4 at index 5
found 3 at index 7
found 1 at index 9

Searching for: [1, 3, 4, 18, 19, 15]
in: [9, 6, 1, 8, 7, 4, 3, 0, 2, 5]
found 1 at index 2
found 4 at index 5
found 3 at index 6
And this is the second program, mult_item_search_unsorted_list_w_arrows.py:
# mult_item_search_unsorted_list_w_arrows.py 
# Purpose: To search for multiple items in an unsorted list.
# Marks the position of the items found with arrows.
# Author: Vasudev Ram
# Copyright 2019 Vasudev Ram
# Training: https://jugad2.blogspot.com/p/training.html
# Blog: https://jugad2.blogspot.com
# Web site: https://vasudevram.github.io
# Product store: https://gumroad.com/vasudevram

from __future__ import print_function
import sys
from random import sample, shuffle

def mult_item_search_unsorted_list(dlist, slist):
for didx, ditem in enumerate(dlist):
for sitem in slist:
if sitem == ditem:
yield (didx, ditem)

def main():
# Create the search list (slist) with some items that will be found
# and some that will not be found in the data list (dlist) below.
slist = sample(range(10), 4) + sample(range(10, 20), 4)
# Create the data list.
dlist = range(10)
for i in range(3):
# Mix it up, DJ.
shuffle(slist)
# MIX it up, DEK.
shuffle(dlist)
print("\nSearching for: {}".format(slist))
print(" in: {}".format(dlist))
for didx, ditem in mult_item_search_unsorted_list(dlist, slist):
print("---------{}^".format('---' * didx))

main()
Output of a run:
$ python mult_item_search_unsorted_list_w_arrows.py

Searching for: [16, 0, 15, 4, 6, 1, 10, 12]
in: [8, 9, 0, 1, 5, 4, 7, 2, 6, 3]
---------------^
------------------^
------------------------^
---------------------------------^

Searching for: [6, 16, 10, 0, 1, 4, 12, 15]
in: [2, 7, 0, 8, 1, 4, 6, 3, 9, 5]
---------------^
---------------------^
------------------------^
---------------------------^

Searching for: [0, 12, 4, 10, 6, 16, 1, 15]
in: [8, 1, 0, 7, 9, 6, 2, 5, 4, 3]
------------^
---------------^
------------------------^
---------------------------------^

In a recent post, Dynamic function creation at run time with Python's eval built-in, I had said:

"Did you notice any pattern to the values of g(i)? The values are 1, 4, 9, 16, 25 - which are the squares of the integers 1 to 5. But the formula I entered for g was not x * x, rather, it was x * x + 2 * x + 1. Then why are squares shown in the output? Reply in the comments if you get it, otherwise I will answer next time."

No reader commented with a solution. So here is a hint to figure it out:

What is the expansion of (a + b) ** 2 (a plus b the whole squared) in algebra?

Heh.

The drawing of the magnifying glass at the top of the post is by:

Yours truly.

( The same one that I used in this post:
Command line D utility - find files matching a pattern under a directory )

I'll leave you with another question: What, if any, could be the advantage of using Python generators in programs like these?
Notice that I said "programs like these", not "these programs".

Enjoy.

- Vasudev Ram - Online Python training and consulting

I conduct online courses on Python programming, Unix / Linux commands and shell scripting and SQL programming and database design, with course material and personal coaching sessions.

The course details and testimonials are here.

Contact me for details of course content, terms and schedule.

Try FreshBooks: Create and send professional looking invoices in less than 30 seconds.

Getting a new web site or blog, and want to help preserve the environment at the same time? Check out GreenGeeks.com web hosting.

Sell your digital products via DPD: Digital Publishing for Ebooks and Downloads.

Learning Linux? Hit the ground running with my vi quickstart tutorial. I wrote it at the request of two Windows system administrator friends who were given additional charge of some Unix systems. They later told me that it helped them to quickly start using vi to edit text files on Unix. Of course, vi/vim is one of the most ubiquitous text editors around, and works on most other common operating systems and on some uncommon ones too, so the knowledge of how to use it will carry over to those systems too.

Check out WP Engine, powerful WordPress hosting.

Get a fast web site with A2 Hosting.

Creating online products for sale? Check out ConvertKit, email marketing for online creators.

Teachable: feature-packed course creation platform, with unlimited video, courses and students.

Posts about: Python * DLang * xtopdf

My ActiveState Code recipes

Follow me on:



from Planet Python
via read more

No comments:

Post a Comment

TestDriven.io: Working with Static and Media Files in Django

This article looks at how to work with static and media files in a Django project, locally and in production. from Planet Python via read...