We present effective algorithms for typical program solutions.
Introduction
In this short tip, we present the importance of science and research in programming and development of the software.
The list of software is as follows:
EasyBlockchain - your digital walletFiesta - antivirus programProjectEnv - model optimization software with open storageTestKit - self-assessment programZines - program for approximate text searching
Four programs from the list above are developed in C#, while Zines is Java project.
Background
There are many algorithms described before like string searching or hash computation, however, they're less efficient than algorithms presented in this tip.
Using the Code
First, let's study the blockchain operation on the digital wallet:
public Blockchain Operation(float f) {
int fi = (int) (f * 100.0f);
string value = "";
int c = fi;
for (int i = 0; i < this.Value.Length; ++i) {
int k = valueOf(this.Value[i]) + c;
c = 0;
while (k < 0) {
k += 16;
--c;
}
while (k >= 16) {
k -= 16;
++c;
}
value += "0123456789abcdef"[k];
}
Blockchain result = new Blockchain(value);
return result;
}
As it can be seen from above, it's linear in performance and handles values with double precision.
The next code handles the subtraction between two hash values in order to obtain the value of the digital storage:
public bool Less(Blockchain bc) {
for (int i = this.Value.Length - 1; i >= 0; --i) {
if (valueOf(this.Value[i]) != valueOf(bc.Value[i])) {
return valueOf(this.Value[i]) < valueOf(bc.Value[i]);
}
}
return false;
}
public float Subtract(Blockchain bc) {
float result = 0;
float p = 1.0f;
int c = 0;
if (this.Less(bc)) {
return -bc.Subtract(this);
}
for (int i = 0; i < this.Value.Length; ++i) {
int a = valueOf(this.Value[i]);
int b = valueOf(bc.Value[i]);
int d = a - b + c;
c = 0;
while (d < 0) {
d += 16;
--c;
}
while (d >= 16) {
d -= 16;
++c;
}
result += p * d;
p *= 16.0f;
}
return result / 100.0f;
}
Here, the Value of Blockchain class is a string.
The Fiesta antivirus software also computes linear hash and thus utilizes the most optimal way of this procedure:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace Fiesta
{
public class Hash
{
public const int HASH_SIZE = 128;
public static byte[] GetHash(Stream stream)
{
int current = 0, b = -1;
byte[] result = new byte[HASH_SIZE];
for (int i = 0; i < result.Length; ++i)
{
result[i] = 0;
}
while ((b = stream.ReadByte()) != -1)
{
result[current] = (byte) ((int) result[current] ^ b);
current = (current + 1) % HASH_SIZE;
}
return result;
}
}
}
This hash further is used within the tries or Aho-Corasick trees in order to search another equal hash.
The ProjectEnv application aims at optimizing the total dispersion of the variable number of factors and is solved using Dynamic Programming (DP) approach:
public void Optimize(int m)
{
int n = 1;
for (int i = 0; i < this.Factors.Count; ++i)
{
Factor f = (Factor)this.Factors[i];
n += (int)Math.Round(f.Dispersion * 100.0);
}
int[,] opt = new int[n, m + 1];
int[,] next_n = new int[n, m + 1];
int[,] next_m = new int[n, m + 1];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j <= m; ++j)
{
opt[i, j] = -1;
next_n[i, j] = -1;
next_m[i, j] = -1;
}
}
opt[0, 0] = 0;
for (int i = 0; i < this.Factors.Count; ++i)
{
Factor f = (Factor)this.Factors[i];
int d = (int)Math.Round(f.Dispersion * 100.0);
f.IsOptimal = false;
for (int k = m; k >= 1; --k)
{
for (int j = n - 1; j >= 0; --j)
{
if (j >= d && opt[j - d, k - 1] != -1 && opt[j, k] == -1)
{
opt[j, k] = opt[j - d, k - 1] + d;
next_n[j, k] = j - d;
next_m[j, k] = i;
}
}
}
}
int found = -1;
for (int i = 0; i < n; ++i)
{
if (opt[i, m] >= 0)
{
found = i;
break;
}
}
if (found >= 0)
{
for (int i = m; i > 0; --i)
{
Factor f = (Factor)this.Factors[next_m[found, i]];
f.IsOptimal = true;
found = next_n[found, i];
}
}
}
The TestKit program uses parsing techniques in order to obtain the object model for further usage in HyperText Markup Language (HTML):
using System;
using System.Collections;
using System.Collections.Generic;
namespace TestKit
{
public class Question
{
public string text;
public ArrayList answers = new ArrayList();
public Question(Stream stream)
{
this.text = "";
while (!stream.atEnd() && stream.current != ':') {
this.text += (char) stream.current;
stream.Read();
}
stream.Read();
this.text = this.text.Trim();
while (!stream.atEnd()) {
Answer answer = new Answer(stream);
this.answers.Add(answer);
if (answer.isFinal) break;
}
}
}
}
The Answer class is defined same as above within the parsing techniques:
using System;
namespace TestKit
{
public class Answer
{
public string text;
public bool isFinal = false;
public bool isCorrect = false;
public static void parseBlanks(Stream stream) {
while (" \r\n\t\v".IndexOf((char) stream.current) >= 0 && !stream.atEnd()) {
stream.Read();
}
}
public Answer(Stream stream)
{
parseBlanks(stream);
if (stream.current == '+') {
this.isCorrect = true;
stream.Read();
}
this.text = "";
while (!stream.atEnd() && stream.current != ';') {
if (stream.current == '.') {
this.isFinal = true;
break;
}
this.text += (char) stream.current;
stream.Read();
}
stream.Read();
this.text = this.text.Trim();
}
}
}
Zines Java program uses the approximate algorithm with sliding window and utilizes Result class defined as follows:
package com.zines;
public class Result {
public String path = null;
public int length = -1;
public int offset = -1;
public String query = null;
public float ratio = 0.0f;
public String text = null;
public Result() {
}
public static void printlnHeader() {
System.out.println("\"FILE\",\"OFFSET\",\"LENGTH\",\"RATIO\"");
}
public void println() {
System.out.println("\""
+ this.path + "\","
+ this.offset
+ ","
+ this.length + ","
+ this.ratio + "");
}
}
Points of Interest
Thus, we have learned how science and programming co-operate together in order to solve problems like optimization and easy way of solution without writing unnecessary excess code.
From all the above, however, it follows that state of the art algorithms are still applicable if there's no scientific approach.
History
- 27th October, 2022 - Initial release
- 2nd November, 2022 - Removed links
- 3rd November, 2022 - Links deleted
- 4th November, 2022 - License changed
