From 21577824dbea88b590dd8b61b5a72c18f9697708 Mon Sep 17 00:00:00 2001
From: Samo Penic <samo.penic@gmail.com>
Date: Wed, 23 Oct 2019 18:02:37 +0000
Subject: [PATCH] Talk finished and debugged
---
hashtables.html | 164 +++++++++++++++++++++++++++++++++++-------------------
1 files changed, 107 insertions(+), 57 deletions(-)
diff --git a/hashtables.html b/hashtables.html
index 084cf3f..5314c87 100644
--- a/hashtables.html
+++ b/hashtables.html
@@ -74,7 +74,8 @@
memory[hashval]=data_index;
insert_idx++;
- if(insert_idx==8){
+ if(insert_idx==13){
+ document.getElementById("currll").innerHTML="DONE!";
alert("Completed!");
}
else {
@@ -89,11 +90,11 @@
if(data_index==-1) data_index=insert_idx;
hashval=hash(names[data_index]);
console.log("f"+hashval);
+ oldhashval=hashval;
while(backupmemory[hashval]!=-1) hashval=(hashval+1)%13;
backupmemory[hashval]=data_index;
insert_idx++;
insert_index_without_collision++;
- //else {
console.log(names[data_index] + "==> REMAPPED ==>" + hashval);
el1=document.getElementById("o"+hashval);
@@ -101,9 +102,13 @@
el1.innerHTML=names[data_index];
el2.innerHTML=phones[data_index];
- if(insert_idx==8){
- alert("Completed!");
+ if(oldhashval!=hashval){
+ el1.style.color="red";
+ el2.style.color="red";
+ }
+ if(insert_idx==13){
document.getElementById("open1current").innerHTML="DONE!";
+ alert("Completed!");
} else{
currentInner(document.getElementById("open1current"), insert_idx);
}
@@ -138,7 +143,7 @@
memory[hashval]=data_index;
backupmemory[hashval]=data_index;
insert_idx++;
- if(insert_idx==8){
+ if(insert_idx==13){
alert("Completed!");
}
else {
@@ -159,10 +164,15 @@
document.getElementById("name5").value,
document.getElementById("name6").value,
document.getElementById("name7").value,
- document.getElementById("name8").value
+ document.getElementById("name8").value,
+ document.getElementById("name9").value,
+ document.getElementById("name10").value,
+ document.getElementById("name11").value,
+ document.getElementById("name12").value,
+ document.getElementById("name13").value
];
- phones=[1,2,3,4,5,6,7,8]
- for(i=0;i<8;i++){
+ phones=[1,2,3,4,5,6,7,8,9,10,11,12,13]
+ for(i=0;i<13;i++){
phones[i]="(01)"+Math.floor((Math.random() * 9000) + 1000)+"-"+Math.floor((Math.random() * 900) + 100);
}
memory=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1];
@@ -181,7 +191,6 @@
document.getElementById("n3").innerHTML=phones[3];
//
document.getElementById("intro0").innerHTML=names[0];
-document.getElementById("intro1").innerHTML=names[0];
document.getElementById("s0result").innerHTML=document.getElementById("s0").innerHTML;
document.getElementById("s3value").innerHTML=document.getElementById("s3").innerHTML;
document.getElementById("s0number").innerHTML=document.getElementById("n0").innerHTML;
@@ -190,7 +199,6 @@
/*Filling the values into array demo until collision occurs */
currentInner(document.getElementById("s1current"), 0);
-/*end demo until collision*/
}
@@ -199,12 +207,13 @@
<div id="naslovnica" class="step slide" data-x="-1000" data-y="-1500">
- <h1>Hardware Meetup - Sputnik, 24. october 2019</h1>
+ <h1>Hardware Meetup - Sputnik, 24. October 2019</h1>
<q>Hash tables</q><br />
- <p class="center"> ... the background of their implementations.</p><br />
+ <p class="center"> ... the basic background of their implementations.</p><br />
<p class="footnote">Samo Penič</p>
+ <img src="images/hashtag.png" style="width:500px" />
</div>
<!--
@@ -235,28 +244,13 @@
</div>
-<div class="step slide vsebina" data-x="-250" data-y="-500" data-z="750" data-rotate-x="90">
- <h1 class="naslov">Let's fill in the data...</h1>
- <form>
- <ol>
- </li> Name: <input id="name1"></input><br />
- </li> Name: <input id="name2"></input><br />
- </li> Name: <input id="name3"></input><br />
- </li> Name: <input id="name4"></input><br />
- </li> Name: <input id="name5"></input><br />
- </li> Name: <input id="name6"></input><br />
- </li> Name: <input id="name7"></input><br />
- </li> Name: <input id="name8"></input><br />
- </ol><br /><br />
- <button onClick="loadNames()">Save data</button>
- </form>
-</div>
<div class="step slide vsebina" data-x="0" data-y="-1500" data-z="0">
<h1 class="naslov">What is a hash table</h1>
<p>Sometimes also called associative array or dictionary. <b>It is a data structure used to map key into values</b></p>
<br /><br />
- <p class="center" style="font-size:18pt">data["<span id='intro0'>Yoda</span>"] gives us all the information stored for <span id="intro1">Yoda</span>.</p>
+ <p class="center">phone_number["<span id='intro0'>Yoda</span>"]</p><br />
+ <p class="center" style="font-size:18pt"> stores and returns us the information stored for varible, object, ...</p>
<br /><br />
<p style="font-size:18pt">It is widely used to build things such us dictionaries, telephone books, book indexes, ...</p><br />
<p>Hash table provide <b>Insertion, Deletion and Retreival</b> in <b>constant time</b>!</p>
@@ -267,13 +261,13 @@
<div class="step slide vsebina" data-x="1000" data-y="-1500" data-z="0">
<h1 class="naslov">However...</h1>
- <p class="" style="margin-bottom:30px">The memory is accessible by addressing the data numerically.</p>
+ <p class="" style="margin-bottom:30px">The computer memory is accessible by addressing the data numerically.</p>
- <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">data[0]</div><div id="s0">Yoda</div><div id="n0" style="font-size:15pt">(01)123-1234</div></span>
- <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">data[1]</div><div id="s1">Obi</div><div id="n1" style="font-size:15pt">(01)222-2222</div></span>
- <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">data[2]</div><div id="s2">Luke</div><div id="n2" style="font-size:15pt">(01)123-1234</div></span>
- <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">data[3]</div><div id="s3">Darth</div><div id="n3" style="font-size:15pt">(01)111-1111</div></span>
- <p style="margin-top:30px;font-size:15pt">e.g.: Accessing the item at memory location data[0] yields name of the person <b><span id="s0result">Yoda</span></b> and person's phone number: <span id="s0number">(01)123-1234</span></p><br />
+ <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">phone[0]</div><div id="s0">Yoda</div><div id="n0" style="font-size:15pt">(01)321-4321</div></span>
+ <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">phone[1]</div><div id="s1">Obi</div><div id="n1" style="font-size:15pt">(01)222-2222</div></span>
+ <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">phone[2]</div><div id="s2">Luke</div><div id="n2" style="font-size:15pt">(01)123-1234</div></span>
+ <span style="width:150px;height:110px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white">phone[3]</div><div id="s3">Darth</div><div id="n3" style="font-size:15pt">(01)111-1111</div></span>
+ <p style="margin-top:30px;font-size:15pt">e.g.: Accessing the item at memory location phone[0] yields name <b><span id="s0result">Yoda</span></b> and his phone number: <span id="s0number">(01)321-4321 (order reversed it is)</span></p><br />
<p>Finding phone number of <span id="s3value">Darth</span> requires linear search through the array, which is not efficient.</p>
@@ -282,6 +276,38 @@
<!-- <div id="overview" class="step" data-x="3000" data-y="1500" data-z="0" data-scale="10">
</div>
-->
+
+<div class="step slide vsebina" data-x="1000" data-y="-500" data-z="750" data-rotate-x="90">
+ <h1 class="naslov">Builing a phonebook...</h1>
+ <form>
+ <table style="width:100%;">
+<col width="70%">
+ <col width="30%">
+ <tr>
+ <td>
+ <ol style="font-size:16pt;">
+ </li> Name: <input id="name1"></input><br />
+ </li> Name: <input id="name2"></input><br />
+ </li> Name: <input id="name3"></input><br />
+ </li> Name: <input id="name4"></input><br />
+ </li> Name: <input id="name5"></input><br />
+ </li> Name: <input id="name6"></input><br />
+ </li> Name: <input id="name7"></input><br />
+ </li> Name: <input id="name8"></input><br />
+ </li> Name: <input id="name9"></input><br />
+ </li> Name: <input id="name10"></input><br />
+ </li> Name: <input id="name11"></input><br />
+ </li> Name: <input id="name12"></input><br />
+ </li> Name: <input id="name13"></input><br />
+ </ol>
+ </td>
+ <td>
+ <button onClick="loadNames()">Save data</button><br />
+ </td>
+ </tr>
+ </table>
+ </form>
+</div>
<div class="step slide vsebina" data-x="2000" data-y="-1500" data-z="0">
@@ -294,19 +320,19 @@
<button onclick="insertIntoMemory(-1);">Insert</button>
<br /><br />
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[0]</div><div id="f0" style="font-size:18px"> </div><div id="nf0" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[1]</div><div id="f1" style="font-size:18px"> </div><div id="nf1" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[2]</div><div id="f2" style="font-size:18px"> </div><div id="nf2" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[3]</div><div id="f3" style="font-size:18px"> </div><div id="nf3" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[4]</div><div id="f4" style="font-size:18px"> </div><div id="nf4" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[5]</div><div id="f5" style="font-size:18px"> </div><div id="nf5" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[6]</div><div id="f6" style="font-size:18px"> </div><div id="nf6" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[7]</div><div id="f7" style="font-size:18px"> </div><div id="nf7" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[8]</div><div id="f8" style="font-size:18px"> </div><div id="nf8" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[9]</div><div id="f9" style="font-size:18px"> </div><div id="nf9" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[10]</div><div id="f10" style="font-size:18px"> </div><div id="nf10" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[11]</div><div id="f11" style="font-size:18px"> </div><div id="nf11" style="font-size:11pt"> </div></span>
- <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">data[12]</div><div id="f12" style="font-size:18px"> </div><div id="nf12" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[0]</div><div id="f0" style="font-size:18px"> </div><div id="nf0" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[1]</div><div id="f1" style="font-size:18px"> </div><div id="nf1" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[2]</div><div id="f2" style="font-size:18px"> </div><div id="nf2" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[3]</div><div id="f3" style="font-size:18px"> </div><div id="nf3" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[4]</div><div id="f4" style="font-size:18px"> </div><div id="nf4" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[5]</div><div id="f5" style="font-size:18px"> </div><div id="nf5" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[6]</div><div id="f6" style="font-size:18px"> </div><div id="nf6" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[7]</div><div id="f7" style="font-size:18px"> </div><div id="nf7" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[8]</div><div id="f8" style="font-size:18px"> </div><div id="nf8" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[9]</div><div id="f9" style="font-size:18px"> </div><div id="nf9" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[10]</div><div id="f10" style="font-size:18px"> </div><div id="nf10" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[11]</div><div id="f11" style="font-size:18px"> </div><div id="nf11" style="font-size:11pt"> </div></span>
+ <span style="width:90px;height:100px;border:1px solid #000;margin:0px;display:inline-block;margin-left:-8px;"><div style="background:grey;color:white;font-size:18px">phone[12]</div><div id="f12" style="font-size:18px"> </div><div id="nf12" style="font-size:11pt"> </div></span>
</div>
@@ -314,14 +340,14 @@
<div class="step slide vsebina" data-x="2000" data-y="-1500" data-z="-1500">
<h1 class="naslov">Collisions!</h1>
- <p>They will occur. The probability depends on Load factor (LF=number_of_items/array_size)</p>
+ <p>They will occur. The probability depends on Load factor (LF=number_of_items/array_size)</p><br />
- <p>We can cope with collisions in multitude of ways:</p>
+ <p>We can cope with collisions in different of ways:</p><br />
<ul>
<li>Closed addressing (chaining)
- <li>Open addressing (linear probing) (million ways how to do it)
- <li>using alternate hash functions (million ways how to do it)
- <li>Resize array ;) (not a scientific way to do it)
+ <li>Open addressing (linear probing)
+ <li>using alternate hash functions
+ <li>Resize the array ;)
</ul>
</div>
@@ -385,21 +411,45 @@
<div class="step slide vsebina" data-x="3000" data-y="-1500" data-z="0">
- <h1 class="naslov">Hash function properties</h1>
+ <h1 class="naslov">Hash function has to...</h1>
<ul>
- <li>Hash function should minimize collisions
- <li>Uniformly distribute hash values
- <li>Are easy to calculate
+ <li>minimize collisions
+ <li>uniformly distribute hash values
+ <li>be easy to calculate
</ul>
</div>
<div class="step slide vsebina" data-x="4000" data-y="-1500" data-z="0" data-rotate="90">
<h1 class="naslov">Python dictionaries</h1>
+ <p>Python relys heavily on dictionaries, so it is important they are efficient. Uses open addressing multihash to minimize collisions.</p>
+ <pre style="font-size:15pt;margin-top:-10px">
+<code>
+table = [None] * n;
+for hash, key, value in entries:
+ perturb = hash
+ i = hash % n
+ while table[i] is not None:
+ #collision
+ i = (5 * i * perturb + 1) % n
+ perturb >>= 5
+ table[i] = (key, value)
+</code></pre>
+
+ <p>See talk: Raymond Hettinger -- Modern dictionaries (SF Python 2006)</p>
</div>
<div class="step slide vsebina" data-x="4000" data-y="-2500" data-z="0" data-rotate="90">
<h1 class="naslov">Hash tables in firmware</h1>
+ <ul>
+ <li>Hash tables have average time complexity around O(1) for I,L,D
+ <li>Do not resize tables - plan in advance
+ <li>Use the power of prime numbers
+ <li>Storing pointers of data in hash is not a bad idea (!)
+ <ul style="margin-left:50px">
+ <li>to save memory, when data is large
+ <li>to get ordered dict if needed
+ </ul>
</div>
--
Gitblit v1.9.3