From 0d52a3fb8927cb46709001600afb7ffa2474471f Mon Sep 17 00:00:00 2001
From: Samo Penic <samo.penic@gmail.com>
Date: Wed, 23 Oct 2019 13:54:16 +0000
Subject: [PATCH] Added linked list
---
docker.html | 300 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
1 files changed, 289 insertions(+), 11 deletions(-)
diff --git a/docker.html b/docker.html
index 541d0d6..c338e7c 100644
--- a/docker.html
+++ b/docker.html
@@ -14,6 +14,23 @@
<link rel="shortcut icon" href="favicon.png" />
<link rel="apple-touch-icon" href="apple-touch-icon.png" />
+ <style>
+div.linkedlist{
+width:120px;height:35px;border:1px solid #000;font-size:16px;display:inline-block;padding-left:10px;margin-left:30px;
+}
+div.linkedlist::before{
+ content: '\1F82A';
+ font-size: 16pt;
+ left: -1.5em;
+ margin-top:-5px;
+ position: relative;
+}
+
+div.addrvertical{
+width:90px;height:35px;border:1px solid #000;background:grey;color:white;font-size:16px;display:inline-block
+}
+
+ </style>
</head>
<body class="impress-not-supported">
@@ -24,6 +41,124 @@
</div>
<div id="impress">
+<script>
+var names;
+var phones;
+var memory;
+var insert_idx=0;
+var insert_idx_without_collision=0;
+function hash(stringval){
+ hashval= 0;
+ strlen=stringval.length;
+ i=0;
+ for(i=0;i<strlen;i++){
+ hashval=hashval+stringval.charCodeAt(0);
+ }
+ console.log(stringval + " == " + hashval %13);
+ return hashval % 13;
+}
+
+function currentInner(element,data_index){
+ element.innerHTML="Inserting <b>"+names[data_index]+ "</b>. Calculated hash_function is: <b>" + hash(names[data_index])+"</b>";
+}
+
+
+
+function insertMissingIntoLL(data_index){
+ if(data_index==-1) data_index=insert_idx;
+ hashval=hash(names[data_index]);
+ console.log("f"+hashval);
+ elll=document.getElementById("ll"+hashval);
+ elll.innerHTML=elll.innerHTML+"<div class='linkedlist'>"+names[data_index]+"</div>";
+
+ memory[hashval]=data_index;
+ insert_idx++;
+ if(insert_idx==8){
+ alert("Completed!");
+ }
+ else {
+ currentInner(document.getElementById("s1current"), insert_idx);
+ currentInner(document.getElementById("currll"), insert_idx);
+ }
+
+}
+
+
+function insertIntoMemory(data_index){
+ if(data_index==-1) data_index=insert_idx;
+ hashval=hash(names[data_index]);
+ console.log("f"+hashval);
+ if(memory[hashval]!=-1){
+ alert("Collision!!!");
+ insert_index_without_collision=insert_idx;
+ }
+ else{
+ el1=document.getElementById("f"+hashval);
+ el2=document.getElementById("nf"+hashval);
+
+ el1.innerHTML=names[data_index];
+ el2.innerHTML=phones[data_index];
+
+ elll=document.getElementById("ll"+hashval);
+ elll.innerHTML=elll.innerHTML+"<div class='linkedlist'>"+names[data_index]+"</div>";
+
+ memory[hashval]=data_index;
+ insert_idx++;
+ if(insert_idx==8){
+ alert("Completed!");
+ }
+ else {
+ currentInner(document.getElementById("s1current"), insert_idx);
+ currentInner(document.getElementById("currll"), insert_idx);
+ }
+ }
+}
+
+
+function loadNames(){
+ names=[
+ document.getElementById("name1").value,
+ document.getElementById("name2").value,
+ document.getElementById("name3").value,
+ document.getElementById("name4").value,
+ document.getElementById("name5").value,
+ document.getElementById("name6").value,
+ document.getElementById("name7").value,
+ document.getElementById("name8").value
+ ];
+ phones=[1,2,3,4,5,6,7,8]
+ for(i=0;i<8;i++){
+ phones[i]="(01)"+Math.floor((Math.random() * 1000) + 1)+"-"+Math.floor((Math.random() * 1000) + 1);
+ }
+ memory=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1];
+
+
+/* Slide 1 actions */
+//Names goes into storages s0-s4 on first slide...
+document.getElementById("s0").innerHTML=names[0];
+document.getElementById("s1").innerHTML=names[1];
+document.getElementById("s2").innerHTML=names[2];
+document.getElementById("s3").innerHTML=names[3];
+document.getElementById("n0").innerHTML=phones[0];
+document.getElementById("n1").innerHTML=phones[1];
+document.getElementById("n2").innerHTML=phones[2];
+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("s0result").innerHTML=document.getElementById("n0").innerHTML;
+/* End Slide 1 */
+
+/*Filling the values into array demo until collision occurs */
+
+currentInner(document.getElementById("s1current"), 0);
+/*end demo until collision*/
+
+}
+
+
+</script>
<div id="naslovnica" class="step slide" data-x="-1000" data-y="-1500">
@@ -51,31 +186,174 @@
-->
<div class="step slide vsebina" data-x="-250" data-y="-1250" data-z="1500">
- <h1 class="naslov">O meni...</h1>
+ <h1 class="naslov">About me...</h1>
<img class="samo" src="images/Samo1.png">
<ul>
- <li> Elektronik in "ljubiteljski" odprtokodnik</li>
- <li> Asistent na Fakulteti za elektrotehniko vodim vaje iz predmetov OET</li>
- <li> Od leta 2016 sodelujem pri izvajanju obštudijske dejavnosti <b>Praktični primeri uporabe odprte kode</b></li>
- <li> Programer entuzijast </li>
+ <li> phD in Electrical engineering</li>
+ <li> working at the Faculty of electrical engineering, teaching fundamentals of EM fields</li>
+ <li> promoting open source since... ever?</li>
+ <li> hobby programmer </li>
</ul>
</div>
- <div class="step slide vsebina" data-x="0" data-y="-1500" data-z="0">
- <h1 class="naslov">Kaj so kontejnerji?</h1>
+<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>
- <p class="">Kontejner (vsebnik, zabojnik) je oblika enkapsulacije aplikacij</p>
+<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>
+ <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>
+</div>
+
+
+
+ <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>
-<!-- <img src="images/container-app.jpg" style="width:800px;"> -->
-
- <p>Zapiranje applikacij v kontejnerje je nekje med popolno virtualizacijo in zagonom aplikacije v gostiteljevem okolju.</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"></span>(01)123-1234</p><br />
+
+ <p>Finding phone number of <span id="s3value">Darth</span> requires linear search through the array, which is not efficient.</p>
+
</div>
<!-- <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="2000" data-y="-1500" data-z="0">
+ <h1 class="naslov">Mapping key to index</h1>
+
+ <p>... is performed by so called hash functions. It can be as simple as <b>sum(ascii_code[i]) % array_size</b></p><br />
+
+ <p>Let's try it out for our phone directory (array_size=13):</p><br />
+ <div id="s1current"></div><br />
+ <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>
+
+ </div>
+
+
+ <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>We can cope with collisions in multitude of ways:</p>
+ <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)
+ </ul>
+ </div>
+
+
+ <div class="step slide vsebina" data-x="2000" data-y="-2500" data-z="0">
+ <h1 class="naslov">Closed addressing</h1>
+ <table style="width:100%">
+<col width="70%">
+ <col width="30%">
+ <tr>
+ <td>
+ <div id='ll0'><div class="addrvertical">data[0]</div></div>
+ <div id='ll1'><div class="addrvertical">data[1]</div></div>
+ <div id='ll2'><div class="addrvertical">data[2]</div></div>
+ <div id='ll3'><div class="addrvertical">data[3]</div></div>
+ <div id='ll4'><div class="addrvertical">data[4]</div></div>
+ <div id='ll5'><div class="addrvertical">data[5]</div></div>
+ <div id='ll6'><div class="addrvertical">data[6]</div></div>
+ <div id='ll7'><div class="addrvertical">data[7]</div></div>
+ <div id='ll8'><div class="addrvertical">data[8]</div></div>
+ <div id='ll9'><div class="addrvertical">data[9]</div></div>
+ <div id='ll10'><div class="addrvertical">data[10]</div></div>
+ <div id='ll11'><div class="addrvertical">data[11]</div></div>
+ <div id='ll12'><div class="addrvertical">data[12]</div></div>
+ <div id='ll13'><div class="addrvertical">data[13]</div></div>
+ </td>
+ <td>
+ <div id="currll"></div>
+ <button onclick="insertMissingIntoLL(-1);">Insert</button>
+
+</td>
+
+ </tr>
+</table>
+
+ </div>
+
+
+ <div class="step slide vsebina" data-x="2000" data-y="-3500" data-z="0">
+ <h1 class="naslov">Open addressing</h1>
+
+ </div>
+
+
+
+ <div class="step slide vsebina" data-x="3000" data-y="-1500" data-z="0">
+ <h1 class="naslov">Hash function properties</h1>
+ <ul>
+ <li>Hash function should minimize collisions
+ <li>Uniformly distribute hash values
+ <li>Are 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>
+ </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>
+ </div>
+
+
+ <div id="overview" class="step" data-x="3000" data-y="1500" data-z="0" data-scale="10">
+ </div>
+
+
+
</div>
<div id="impress-toolbar"></div>
--
Gitblit v1.9.3