Recently, it turned out that users of modern Nvidia GPUs under Arch Linux do not need to use the bumblebee package at all, for example, for me it did not detect an external monitor when connected. I recommend removing the bumblebee package and all related packages, and installing prime using the instructions on the Arch Wiki.
Next, to launch all games on Steam and 3D applications, add prime-run, for Steam this is done like this prime-run %command% in additional launch options.
To check the correctness, you can use glxgears, prime-run glxgears.
https://bbs.archlinux.org/viewtopic.php? pid=2048195#p2048195
Author Archives: demensdeum
Quicksort
Quicksort is a divide-and-conquer sorting algorithm. Recursively, in parts, parse the array of numbers, setting the numbers in the smaller and larger order from the selected pivot element, insert the pivot element itself into the hot-point between them. After a few recursive iterations, you’ll end up with a sorted list. Time complexity O(n2).
Scheme:
- We start with the fact that we get a list of elements outside, sorting boundaries. In the first step, the sort boundaries will be from start to finish.
- Check that the boundaries of the beginning and end do not intersect, if this happens, then it’s time to finish
- Select some element from the list, call it pivot
- Shift to the right to the end to the last index, so as not to interfere
- Create a counter of *smaller numbers* while equal to zero
- Loop through the list from left to right, up to and including the last index where the anchor element is located
- Each element is compared to the pivot
- If it is less than the reference, then we swap it in places according to the index of the counter of smaller numbers. Increment the counter of smaller numbers.
- When the cycle reaches the anchor element, we stop, swap the anchor element with the element by the counter of smaller numbers.
- We run the algorithm separately for the left smaller part of the list, and separately for the right most part of the list.
- As a result, all recursive iterations will start to stop due to the check in paragraph 2
- Get sorted list
Quicksort was invented by the scientist Charles Antony Richard Hoare at Moscow State University, having learned Russian, he studied computer translation, as well as probability theory at the Kolmogorov school. In 1960, due to a political crisis, he left the Soviet Union.
An example implementation in Rust:
extern crate rand;
use rand::Rng;
fn swap(numbers: &mut [i64], from: usize, to: usize) {
let temp = numbers[from];
numbers[from] = numbers[to];
numbers[to] = temp;
}
fn quicksort(numbers: &mut [i64], left: usize, right: usize) {
if left >= right {
return
}
let length = right - left;
if length <= 1 {
return
}
let pivot_index = left + (length / 2);
let pivot = numbers[pivot_index];
let last_index = right - 1;
swap(numbers, pivot_index, last_index);
let mut less_insert_index = left;
for i in left..last_index {
if numbers[i] < pivot {
swap(numbers, i, less_insert_index);
less_insert_index += 1;
}
}
swap(numbers, last_index, less_insert_index);
quicksort(numbers, left, less_insert_index);
quicksort(numbers, less_insert_index + 1, right);
}
fn main() {
let mut numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
let mut reference_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
let mut rng = rand::thread_rng();
for i in 0..numbers.len() {
numbers[i] = rng.gen_range(-10..10);
reference_numbers[i] = numbers[i];
}
reference_numbers.sort();
println!("Numbers {:?}", numbers);
let length = numbers.len();
quicksort(&mut numbers, 0, length);
println!("Numbers {:?}", numbers);
println!("Reference numbers {:?}", reference_numbers);
if numbers != reference_numbers {
println!("Validation failed");
std::process::exit(1);
}
else {
println!("Validation success!");
std::process::exit(0);
}
}
If you don't understand anything, I suggest watching a video by Rob Edwards from the San Diego State University https://www.youtube.com/watch?v=ZHVk2blR45Q it most simply, step by step, shows the essence and implementation of the algorithm.
Links
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/quickSort
References
https://www.youtube.com/watch?v=4s-aG6yGGLU
https://www.youtube.com/watch?v=ywWBy6J5gz8
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://ru.wikipedia.org/wiki/Быстрая_сортировка
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://www.youtube.com/watch?v=XE4VP_8Y0BU
https://www.youtube.com/watch?v=MZaf_9IZCrc
https://www.youtube.com/watch?v=ZHVk2blR45Q
http://rosettacode.org/wiki/Sorting_algorithms/Quicksort
https://www.youtube.com/watch?v=4s-aG6yGGLU
https://www.youtube.com/watch?v=dQw4w9WgXcQ
https://www.youtube.com/watch?v=maibrCbZWKw
https://www.geeksforgeeks.org/quick-sort/
https://www.youtube.com/watch?v=uXBnyYuwPe8
Binary Insertion Sort
Binary Insertion Sort is a variant of insertion sort in which the insertion position is determined using a binary search. The time complexity of the algorithm is O(n2)
The algorithm works like this:
- Loop from zero to end of list
- In the loop, a number is selected for sorting, the number is stored in a separate variable
- Binary search looks for the index to insert this number against the numbers on the left
- After finding the index, the numbers on the left are shifted one position to the right, starting at the insertion index. The process will erase the number to be sorted.
- The previously stored number is inserted at the insertion index
- At the end of the loop, the entire list will be sorted
During a binary search, it is possible that the number will not be found, but the index is not returned. Due to the peculiarities of the binary search, the number closest to the desired one will be found, then to return the index it will be necessary to compare it with the desired one, if the desired one is less, then the desired one should be at the index on the left, and if it is greater or equal, then on the right.
Source code in Go:
package main
import (
"fmt"
"math/rand"
"time"
)
const numbersCount = 20
const maximalNumber = 100
func binarySearch(numbers []int, item int, low int, high int) int {
for high > low {
center := (low + high) / 2
if numbers[center] < item { low = center + 1 } else if numbers[center] > item {
high = center - 1
} else {
return center
}
}
if numbers[low] < item {
return low + 1
} else {
return low
}
}
func main() {
rand.Seed(time.Now().Unix())
var numbers [numbersCount]int
for i := 0; i < numbersCount; i++ {
numbers[i] = rand.Intn(maximalNumber)
}
fmt.Println(numbers)
for i := 1; i < len(numbers); i++ { searchAreaLastIndex := i - 1 insertNumber := numbers[i] insertIndex := binarySearch(numbers[:], insertNumber, 0, searchAreaLastIndex) for x := searchAreaLastIndex; x >= insertIndex; x-- {
numbers[x+1] = numbers[x]
}
numbers[insertIndex] = insertNumber
}
fmt.Println(numbers)
}
Links
References
https://www.geeksforgeeks.org/binary-insertion-sort/
https://www.youtube.com/watch?v=-OVB5pOZJug
Shell Sort
Shell Sort is a variant of sorting by inserts with preliminary combing of an array of numbers.
We need to remember how insertion sort works:
- The loop starts from zero to the end of the loop, thus the array is divided into two parts
- For the left side, the second loop is started, comparing elements from right to left, the smaller element on the right is omitted until there is a smaller element on the left
- At the end of both cycles, we get a sorted list
Once in a while, computer scientist Donald Shell wondered how to improve the insertion sort algorithm. He came up with the idea to preliminarily go through the array with two cycles, but at a certain distance, gradually reducing the “comb” until it turns into a regular insertion sort algorithm. Everything is really so simple, no pitfalls, we add another one to the two cycles from above, in which we gradually reduce the size of the “comb”. The only thing that will need to be done is to check the distance when comparing so that it does not go beyond the array.
A really interesting topic is the choice of sequence for changing the length of the comparison at each iteration of the first loop. It is interesting for the reason that the performance of the algorithm depends on it.
A table of known variants and time complexity can be viewed here:
https://en.wikipedia.org/wiki/Shellsort#Gap_sequences
Different people were engaged in calculating the ideal distance, so, apparently, this topic was interesting to them. Couldn’t they just fire up Ruby, call the fastest sort() algorithm?
In general, these strange people wrote dissertations on the topic of calculating the distance / gap of the “comb” for the Shell algorithm. I just used the results of their work and checked 5 types of sequences, Hibbard, Knuth-Pratt, Ciura, Sedgewick.
from typing import List
import time
import random
from functools import reduce
import math
DEMO_MODE = False
if input("Demo Mode Y/N? ").upper() == "Y":
DEMO_MODE = True
class Colors:
BLUE = '\033[94m'
RED = '\033[31m'
END = '\033[0m'
def swap(list, lhs, rhs):
list[lhs], list[rhs] = list[rhs], list[lhs]
return list
def colorPrintoutStep(numbers: List[int], lhs: int, rhs: int):
for index, number in enumerate(numbers):
if index == lhs:
print(f"{Colors.BLUE}", end = "")
elif index == rhs:
print(f"{Colors.RED}", end = "")
print(f"{number},", end = "")
if index == lhs or index == rhs:
print(f"{Colors.END}", end = "")
if index == lhs or index == rhs:
print(f"{Colors.END}", end = "")
print("\n")
input(">")
def ShellSortLoop(numbers: List[int], distanceSequence: List[int]):
distanceSequenceIterator = reversed(distanceSequence)
while distance:= next(distanceSequenceIterator, None):
for sortArea in range(0, len(numbers)):
for rhs in reversed(range(distance, sortArea + 1)):
lhs = rhs - distance
if DEMO_MODE:
print(f"Distance: {distance}")
colorPrintoutStep(numbers, lhs, rhs)
if numbers[lhs] > numbers[rhs]:
swap(numbers, lhs, rhs)
else:
break
def ShellSort(numbers: List[int]):
global ShellSequence
ShellSortLoop(numbers, ShellSequence)
def HibbardSort(numbers: List[int]):
global HibbardSequence
ShellSortLoop(numbers, HibbardSequence)
def ShellPlusKnuttPrattSort(numbers: List[int]):
global KnuttPrattSequence
ShellSortLoop(numbers, KnuttPrattSequence)
def ShellPlusCiuraSort(numbers: List[int]):
global CiuraSequence
ShellSortLoop(numbers, CiuraSequence)
def ShellPlusSedgewickSort(numbers: List[int]):
global SedgewickSequence
ShellSortLoop(numbers, SedgewickSequence)
def insertionSort(numbers: List[int]):
global insertionSortDistanceSequence
ShellSortLoop(numbers, insertionSortDistanceSequence)
def defaultSort(numbers: List[int]):
numbers.sort()
def measureExecution(inputNumbers: List[int], algorithmName: str, algorithm):
if DEMO_MODE:
print(f"{algorithmName} started")
numbers = inputNumbers.copy()
startTime = time.perf_counter()
algorithm(numbers)
endTime = time.perf_counter()
print(f"{algorithmName} performance: {endTime - startTime}")
def sortedNumbersAsString(inputNumbers: List[int], algorithm) -> str:
numbers = inputNumbers.copy()
algorithm(numbers)
return str(numbers)
if DEMO_MODE:
maximalNumber = 10
numbersCount = 10
else:
maximalNumber = 10
numbersCount = random.randint(10000, 20000)
randomNumbers = [random.randrange(1, maximalNumber) for i in range(numbersCount)]
ShellSequenceGenerator = lambda n: reduce(lambda x, _: x + [int(x[-1]/2)], range(int(math.log(numbersCount, 2))), [int(numbersCount / 2)])
ShellSequence = ShellSequenceGenerator(randomNumbers)
ShellSequence.reverse()
ShellSequence.pop()
HibbardSequence = [
0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095,
8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575,
2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727,
268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591
]
KnuttPrattSequence = [
1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720,
797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733,
1743392200, 5230176601, 15690529804, 47071589413
]
CiuraSequence = [
1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376,
10941, 27353, 68383, 170958, 427396, 1068491,
2671228, 6678071, 16695178, 41737946, 104344866,
260862166, 652155416, 1630388541
]
SedgewickSequence = [
1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,
8929, 16001, 36289, 64769, 146305, 260609, 587521,
1045505, 2354689, 4188161, 9427969, 16764929, 37730305,
67084289, 150958081, 268386305, 603906049, 1073643521,
2415771649, 4294770689, 9663381505, 17179475969
]
insertionSortDistanceSequence = [1]
algorithms = {
"Default Python Sort": defaultSort,
"Shell Sort": ShellSort,
"Shell + Hibbard" : HibbardSort,
"Shell + Prat, Knutt": ShellPlusKnuttPrattSort,
"Shell + Ciura Sort": ShellPlusCiuraSort,
"Shell + Sedgewick Sort": ShellPlusSedgewickSort,
"Insertion Sort": insertionSort
}
for name, algorithm in algorithms.items():
measureExecution(randomNumbers, name, algorithm)
reference = sortedNumbersAsString(randomNumbers, defaultSort)
for name, algorithm in algorithms.items():
if sortedNumbersAsString(randomNumbers, algorithm) != reference:
print("Sorting validation failed")
exit(1)
print("Sorting validation success")
exit(0)
mypy
Links
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/shellSort
http://mypy-lang.org/
References
https://dl.acm.org/doi/10.1145/368370.368387
https://en.wikipedia.org/wiki/Shellsort
http://rosettacode.org/wiki/Sorting_algorithms/Shell_sort
https://ru.wikipedia.org/wiki/Сортировка_Шелла
https://neerc.ifmo.ru/wiki/index.php?title=Сортировка_Шелла
https://twitter.com/gvanrossum/status/700741601966985216
Double Selection Sort
Double Selection Sort – a subspecies of sorting by selection, it seems like it should be accelerated twice. The vanilla algorithm double loops through the list of numbers, finds the minimum number, and swaps it with the current digit pointed to by the loop at the level above. Double selection sort, on the other hand, looks for the minimum and maximum number, then it replaces the two digits indicated by the loop at the level above – two numbers on the left and on the right. All this orgy ends when the cursors of numbers to replace meet in the middle of the list, as a result, sorted numbers are obtained to the left and right of the visual center. The time complexity of the algorithm is similar to Selection Sort – O(n2), but supposedly there is a 30% speedup.
Corner case
Already at this stage, you can imagine the moment of collision, when the number of the left cursor (the minimum number) will point to the maximum number in the list, then the minimum number is permuted, the permutation of the maximum number immediately breaks down. Therefore, all implementations of the algorithm contain a check of such cases, replacement of indices with correct ones. In my implementation, one check was enough:
if (leftCursor == maximalNumberIndex) {
maximalNumberIndex = minimalNumberIndex;
}
Cito implementation
Cito is a lib language, a translator language. You can write on it for C, C++, C#, Java, JavaScript, Python, Swift, TypeScript, OpenCL C, while knowing absolutely nothing about these languages. The source code in the Cito language is translated into the source code in the supported languages, then you can use it as a library, or directly by correcting the generated code by hand. A kind of Write once – translate to anything.
Double Selection Sort – Cito:
public class DoubleSelectionSort
{
public static int[] sort(int[]# numbers, int length)
{
int[]# sortedNumbers = new int[length];
for (int i = 0; i < length; i++) {
sortedNumbers[i] = numbers[i];
}
for (int leftCursor = 0; leftCursor < length / 2; leftCursor++) {
int minimalNumberIndex = leftCursor;
int minimalNumber = sortedNumbers[leftCursor];
int rightCursor = length - (leftCursor + 1);
int maximalNumberIndex = rightCursor;
int maximalNumber = sortedNumbers[maximalNumberIndex];
for (int cursor = leftCursor; cursor <= rightCursor; cursor++) { int cursorNumber = sortedNumbers[cursor]; if (minimalNumber > cursorNumber) {
minimalNumber = cursorNumber;
minimalNumberIndex = cursor;
}
if (maximalNumber < cursorNumber) {
maximalNumber = cursorNumber;
maximalNumberIndex = cursor;
}
}
if (leftCursor == maximalNumberIndex) {
maximalNumberIndex = minimalNumberIndex;
}
int fromNumber = sortedNumbers[leftCursor];
int toNumber = sortedNumbers[minimalNumberIndex];
sortedNumbers[minimalNumberIndex] = fromNumber;
sortedNumbers[leftCursor] = toNumber;
fromNumber = sortedNumbers[rightCursor];
toNumber = sortedNumbers[maximalNumberIndex];
sortedNumbers[maximalNumberIndex] = fromNumber;
sortedNumbers[rightCursor] = toNumber;
}
return sortedNumbers;
}
}
Links
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/doubleSelectionSort
https://github.com/pfusik/cito
References
https://www.researchgate.net/publication/330084245_Improved_Double_Selection_Sort_using_Algorithm
http://algolab.valemak.com/selection-double
https://www.geeksforgeeks.org/sorting-algorithm-slightly-improves-selection-sort/
Cocktail Shaker Sort
Cocktail Shaker Sort – sorting in a shaker, a variant of bidirectional bubble sort.
The algorithm works like this:
- Select the starting direction of the iteration in the loop (usually left-to-right)
- Next, the numbers are checked in pairs
- If the next element is larger, they are swapped
- At the end, the iteration process restarts with the direction reversed
- Iterates until there are no more permutations
The time complexity of the algorithm is similar to the bubble one – O(n2) .
An example implementation in PHP:
#!/usr/bin/env php
<?php
function cocktailShakeSort($numbers)
{
echo implode(",", $numbers),"\n";
$direction = false;
$sorted = false;
do {
$direction = !$direction;
$firstIndex = $direction == true ? 0 : count($numbers) - 1;
$lastIndex = $direction == true ? count($numbers) - 1 : 0;
$sorted = true;
for(
$i = $firstIndex;
$direction == true ? $i < $lastIndex : $i > $lastIndex;
$direction == true ? $i++ : $i--
) {
$lhsIndex = $direction ? $i : $i - 1;
$rhsIndex = $direction ? $i + 1 : $i;
$lhs = $numbers[$lhsIndex];
$rhs = $numbers[$rhsIndex];
if ($lhs > $rhs) {
$numbers[$lhsIndex] = $rhs;
$numbers[$rhsIndex] = $lhs;
$sorted = false;
}
}
} while ($sorted == false);
echo implode(",", $numbers);
}
$numbers = [2, 1, 4, 3, 69, 35, 55, 7, 7, 2, 6, 203, 9];
cocktailShakeSort($numbers);
?>
Links
Sources
https://www.youtube.com/watch?v=njClLBoEbfI
https://www.geeksforgeeks.org/cocktail-sort/< br />
https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort
FatBoySize – disk usage information tool
FatBoySize – disk usage information tool, it shows directories, files sizes in terminal.
Supports any OS that support Python 3.
Usage: python3 fbs.py
Verbose mode 1: python3 fbs.py -v
Verbose mode 2: python3 fbs.py --version
Right now it works only for current terminal path.
Result example:
python3 ~/Sources/my/fatboysize/fbs.py
.local -> 145. GB
Downloads -> 103. GB
.cache -> 37.0 GB
.android -> 11.6 GB
Sources -> 8.63 GB
As you can see, directory Downloads is quite large.
Links
https://gitlab.com/demensdeum/fatboysize/
…And Primus for All
In this note I will describe the launch of Steam games on the Linux distribution Arch Linux in the configuration of an Intel + Nvidia laptop
Counter-Strike: Global Offensive
The only configuration that worked for me is Primus-vk + Vulkan.
Install the required packages:
pacman -S vulkan-intel lib32-vulkan-intel nvidia-utils lib32-nvidia-utils vulkan-icd-loader lib32-vulkan-icd-loader primus_vk
Next, add launch options for Counter-Strike: Global Offensive:
pvkrun %command% -vulkan -console -fullscreen
Should work!
Sid Meier’s Civilization VI
Works in conjunction – Primus + OpenGL + LD_PRELOAD.
Install the Primus package:
pacman -S primus
Next, add launch options for Sid Meier’s Civilization VI:
LD_PRELOAD='/usr/lib/libfreetype.so.6:/usr/lib/libbrotlicommon.so.1:/usr/lib/libbrotlidec.so.1' primusrun %command%
LD_PRELOAD pushes the Freetype compression and font libraries.
Dota 2
Works in conjunction – Primus + OpenGL + removal of locks at startup.
Install the Primus package:
pacman -S primus
Next, add launch options for Dota 2:
primusrun %command% -gl -console
If the game doesn’t start with fcntl(5) for /tmp/source_engine_2808995433.lock failed, then try deleting the /tmp/source_engine_2808995433.lock file
rm /tmp/source_engine_2808995433.lock
Usually the lock file is left over from the last game session unless the game was closed naturally.
How to check?
The easiest way to check the launch of applications on a discrete Nvidia graphics card is through the nvidia-smi utility:
For games on the Source engine, you can check through the game console using the mat_info command:
References
https://wiki.archlinux.org/title/Steam/Game-specific_troubleshooting
https://help.steampowered.com/en/faqs/view/145A-FE54-F37B-278A
https://bbs.archlinux.org/viewtopic.php?id=277708