Algoritme: genereren van een unieke string

[umask]

Beste Tweakenaars,

Programmeertaal: C# (versie 7.3)
Ontwikkelomgeving: Visual Studio 2019 Community

Context:
Een algoritme dat ervoor zorgt voor het genereren van een unieke string van 7 karakters lang. Naar mijn idee werkt het goed, want ik heb het meerdere malen keer gecontroleerd met unit tests (automatische testen).

Eisen algoritme:
Dezelfde karakters, bijvoorbeeld 'a' en 'a', mogen niet langs elkaar staan. Het maakt niet uit op welke positie van de array, dit mag niet voorkomen.

Probleem/vraag:
1# Het algoritme is te lang (methode 'GenerateTransactionId') en vroeg ik me af of iemand weet hoe ik dit algoritme eenvoudiger kan maken en nog even snel werkt of zelfs nog sneller/efficiënter zijn taak kan voltooien?

2# Daarnaast kreeg ik een Index OutOfRangeException, daardoor werd ik gedwongen om te kijken of de result array leeg was om vervolgens dan een karakter toe te voegen aan die array. Op die manier zorg ik ervoor dat ik die exception ontkom. Misschien dat u ook hierover wat kan adviseren? Een andere aanpak of iets dergelijks..

Probleem #2 heeft betrekking op de volgende regel code:

C#:

if (result == "")
            result = selectedChar.ToString();

Ik hoor graag uw bevindingen en eventueel wat beter kan. Alvast bedankt .

Hieronder volgt het algoritme met eventueel de bijbehorende variabelen:

C#:

// Fields
private Random randomNum;
private string result = string.Empty;
private int index, indexNew;

private static int[] numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
private static int maxLength = numbers.Count() - 4;

private static char[] alphabetLowChars = new char[]
{
   'a','b','c','d','e','f','g','h','i','j','k','l','m',
   'n','o','p','q','r','s','t','u','v','w','x','y','z'
};

// Methods
public string GenerateTransactionId()
{
    randomNum = new Random();
    for (int i = 0; i < maxLength; i++)
    {
        index = i;
        indexNew = randomNum.Next(0, alphabetLowChars.Count());

        char selectedChar = alphabetLowChars[indexNew];

        if (result == "")
            result = selectedChar.ToString();

        char currentChar = result[index];

        if (currentChar == selectedChar)
        {
                do
                {
                    int tmpNewIndex = randomNum.Next(0, alphabetLowChars.Count());
                    result += alphabetLowChars[tmpNewIndex];

                } while (result[index].Equals(result[index + 1]));
        }
        
        if ((result.Length - i) < result.Length)
                if(result.Length <= maxLength)
                    result += alphabetLowChars[indexNew];
    }

    return result;
}

[ Voor 4% gewijzigd door umask op 10-04-2020 16:52 . Reden: Vergeten methode naam erbij te zetten. ]

[RobIII]

Ik zie nogal wat issues maar de eerste vraag is: waarvoor dient die string? Ik zou persoonlijk een RNGCryptoServiceProvider pakken, die een zwik bytes laten genereren en daar wat chars uit destilleren in een handjevol regels code. Als ik achter een PC zit i.p.v. een mobieltje wil ik wel een voorzetje geven.

umask schreef op vrijdag 10 april 2020 @ 16:46:
Naar mijn idee werkt het goed, want ik heb het meerdere malen keer gecontroleerd met unit tests (automatische testen).

Als unittests érgens niet geschikt voor zijn en als je iets niet wil is 't random dingen; een unittest moet reproduceerbaar zijn, élke keer dat je 'm runt moet je dezelfde waardes zien. Anders krijg je een unittest die de ene keer passed en de andere keer failed; dat kan dus niet.

[ Voor 45% gewijzigd door RobIII op 10-04-2020 17:03 ]

[Gropah]

Een paar vragen/opmerkingen (zonder dat ik specifieke C# kennis heb):

- Waarom is je algoritme te lang?
- Wat is het doel van deze code? Wil je begrijpelijke code? Snelle code? Wil je leren hoe je kan optimaliseren? En op welk gebied wil je optimaliseren?

Verder meer code inhoudelijk:
- Waarom pre-alloceer je niet de ruimte gezien je toch weet hoe lang je string gaat worden?
- Waarom is de maxLength afhankelijk van het aantal in de array nummers? Je hebt het er over dat de ID standaard 7 tekens lang is.
- Je slaat nogal wat dingen op als fields die niet per se in een field zouden moeten hoeven. Als de gegenereerde ID niet gecached hoeft te worden hoeft dat niet daar, idem voor random. Waarom doe je dit? Dit kan nog wel eens probleempjes geven met testbaarheid down the line.

[Philip Ross]

Voor #2: Je doet een random van 0 tot aantal letters. Maar de index loopt altijd van 0 tot aantal-1. Dus als je als random 26 terug krijgt zit je buiten de range van je letters. (van 0 t/m 25)

Oplossing kan zijn om

code:

randomNum.Next(0, alphabetLowChars.Count()-1)

te doen.

Voor wat #1 betreft. Waarom doe je?

code:

private static int[] numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
private static int maxLength = numbers.Count() - 4;

Waar gebruik je dit nummer verder voor? Waarom niet gewoon definieren als 7?

Persoonlijk zou ik overigens niet zelf een array gaan maken maar gewoon naar ascii codering kijken en dan een random int in de range van kleine letters daaruit kiezen. En dan die int in een char omzetten. Dus een random in range 97-122 (http://www.asciitable.com)

dus

code:

indexNew  randomNum.Next(97, 122) en dan char selectedChar = (char)indexNew

Verder kan je ook om opeenvolgende tegen te gaan de int die je uit je random krijgt altijd eerst vergelijken met de vorige en als die gelijk zijn een nieuwe random doen.

[ Voor 8% gewijzigd door Philip Ross op 10-04-2020 17:05 ]

[Voutloos]

Je kan ook t random generen zo dom mogelijk doen en dat dan voor de hele string herhalen als je geen dubbele char requirement faalt.

Of nog eenvoudiger, maar dan heb je iets minder uitkomsten: shuffle gewoon de array met mogelijke chars, pak de eerste n elementen en klaar.

[Gropah]

Voutloos schreef op vrijdag 10 april 2020 @ 17:04:
Je kan ook t random generen zo dom mogelijk doen en dat dan voor de hele string herhalen als je geen dubbele char requirement faalt.

Of nog eenvoudiger, maar dan heb je iets minder uitkomsten: shuffle gewoon de array met mogelijke chars, pak de eerste n elementen en klaar.

Het genereren van random data kan over het algemeen handiger in 1 keer gebeuren. Het schudden van een array met alle letters precies 1 keer kan een slimme zet zijn, mits het geen probleem is dat er geen duplicate characters in zitten (en je dus ook het aantal mogelijkheden beperkt)

[Falcon]

Waarom kan een transactionid (zie zijn method) niet gewoon een GUID zijn?

[edeboeck]

Philip Ross schreef op vrijdag 10 april 2020 @ 17:02:
Voor #2: Je doet een random van 0 tot aantal letters. Maar de index loopt altijd van 0 tot aantal-1. Dus als je als random 26 terug krijgt zit je buiten de range van je letters. (van 0 t/m 25)

Oplossing kan zijn om

code:

randomNum.Next(0, alphabetLowChars.Count()-1)

te doen.

Wat je zegt, klopt niet.

code:

Random.Next(lower, upper);

levert een waarde op in bereik [lower, upper-1]

[edeboeck]

Falcon schreef op vrijdag 10 april 2020 @ 17:11:
Waarom kan een transactionid (zie zijn method) niet gewoon een GUID zijn?

Daaraan was ik ook aan het denken, maar

quote: TS

Eisen algoritme:
Dezelfde karakters, bijvoorbeeld 'a' en 'a', mogen niet langs elkaar staan. Het maakt niet uit op welke positie van de array, dit mag niet voorkomen.

[DataGhost]

Heel leesbaar is je code niet, dat er code staat is duidelijk maar wat je met die code bedoelt (en dat hoeft niet hetzelfde te zijn) is dat niet. Kan je het misschien voorzien van commentaar met daarin je gedachtengang per blokje, en de betekenis/bedoeling van je variabelen? Dan kunnen wij makkelijker beoordelen of je schrijft wat je bedoelt, en of je denkwijze een beetje logisch is.

Ik kan het mis hebben maar op regel 38 staat volgens mij een infinite loop op het moment dat je in de "do" hetzelfde teken genereert als wat op de "index" staat. Verder is het enorm onwaarschijnlijk, maar zo'n loop (als 'ie goed geschreven was) kan alsnog best lang duren als daar elke keer hetzelfde uitkomt. En van het blokje bij regel 41 ben ik reuze benieuwd naar de gedachtengang en hoe dat tot die code heeft geleid.

Het kan in ieder geval met veel minder en veel leesbaardere code zonder inner loop.

[RobIII]

Ik heb zo m'n twijfels bij dit topic. Waarom zou in een transactie-id een letter niet herhaald mogen worden? En waarom beperk je een transactie-id tot (minder dan) 26⁷ ≈ 34 bits? Dat geeft een enorme kans op collisions als je een beetje flink transactie-id's gaat genereren (de kans nadert 100% bij 1 miljoen transacties, of 50% vanaf zo'n 220.000 transacties en nog steeds 1% bij 27.000 transacties). En dan tel ik de beperking dat een letter niet herhaald mag worden nog niet eens mee - dat maakt 't alleen maar erger.

Waarom wordt er geen (G/U)UID gebruikt of, als lengte en leesbaarheid een eis zijn een ULID?

Bij wijze van vingeroefening / corona-verveling kwam ik hier op uit (again: zonder de beperking van herhalende letters - dat is een oefening voor de lezer/topicstarter):

C#:

// Generate cryptographically secure, unbiased, TransactionID
public string GenerateTransactionId(int length = 7)
{
    var bytes = new byte[length * 2];               // Create a small (oversized) buffer
    var result = new char[length];                  // Initialize an array to keep characters in
    var charpointer = 0;                            // Indexer into our result char array
    var rng = new RNGCryptoServiceProvider();       // Get a CSRNG
    
    do
    {
        rng.GetBytes(bytes);                            // (Re)fill buffer

        // Iterate the buffer while the desired string length has not been reached
        for (int i = 0; i < bytes.Length && charpointer < length; i++)
        {
            var c = (char)('a' + (bytes[i] & 0x1F));    // Discard left 3 bits; this will restrict
                                                        // our range of numbers from 0-255 to 0-31
                                                        // without bias; increasing the chance of
                                                        // finding a 0-25 number 8-fold. Then offset
                                                        // with 'a' and convert to char.

            if (c <= 'z')                               // Found a suitable value?
                result[charpointer++] = c;              // Add to result, increment indexer
        }
    } while (charpointer < length);                     // Repeat until we reach the desired length
    return string.Join(string.Empty, result);
}

[Bart2005]

umask schreef op vrijdag 10 april 2020 @ 16:46:
Eisen algoritme:
Dezelfde karakters, bijvoorbeeld 'a' en 'a', mogen niet langs elkaar staan. Het maakt niet uit op welke positie van de array, dit mag niet voorkomen.

Waarom eigenlijk niet? De kracht van "random" is nou juist dat dit wel kan en mag. Random heeft in principe geen regels dus let it flow.

[Bart2005]

RobIII schreef op vrijdag 10 april 2020 @ 18:43:
Ik heb zo m'n twijfels bij dit topic. Waarom zou in een transactie-id een letter niet herhaald mogen worden?

Zeer zeker.

[DataGhost]

Ik denk dat het, gezien de eisen en het niveau van de TS, een programmeeropdracht is om te oefenen of huiswerk ofzo. Niet heel verkeerd om wat logische dingen mee te leren, dus vereenvoudigen van de opdracht lijkt me niet direct gewenst. Vereenvoudigen van de uitkomst wel
@RobIII het is niet moeilijk om in precies length iteraties een TID te maken volgens de eisen in de TS

[RobIII]

DataGhost schreef op vrijdag 10 april 2020 @ 18:56:
@RobIII het is niet moeilijk om in precies length iteraties een TID te maken volgens de eisen in de TS

Als je doelt op de variabele lengte (length argument) dan is dat alleen maar een (makkelijke win) extra'tje. Maar ik heb zélf wat eisen er bij verzonnen zoals geen bias naar bepaalde letters en een CSRNG gebruikt. Als je een oneliner wil kan dat ook hoor Ik wou het alleen niet voorkauwen voor TS maar post wat code ter inspiratie

[DataGhost]

RobIII schreef op vrijdag 10 april 2020 @ 19:01:
[...]

Als je doelt op de variabele lengte (length argument) dan is dat alleen maar een (makkelijke win) extra'tje. Maar ik heb zélf wat eisen er bij verzonnen zoals geen bias naar bepaalde letters en een CSRNG gebruikt. Als je een oneliner wil kan dat ook hoor Ik wou het alleen niet voorkauwen voor TS maar post wat code ter inspiratie

Nja ik bedoelde vooral op het herhalen van de random bij een ongewenste uitkomst wat zowel jij als TS doen (doch in een andere context). Bij jou ligt het ook meer aan hoe het in C moet denk ik, maar ik heb me daarin nooit zo bezig gehouden met random. Ik stel me altijd voor dat het iets is als floor((randomBits(X) / ((1<<X)-1)) * (upper-lower)) + lower of iets anders waardoor je altijd unbiased een getal krijgt binnen je range en dus nooit hoeft te loopen om zo'n getal te krijgen. Maar goed, in jouw ding dus wel, daar lette ik even niet helemaal goed op.

[umask]

RobIII schreef op vrijdag 10 april 2020 @ 16:59:
waarvoor dient die string?

Antwoord:
het doel is om de string te gebruiken als een 'unieke id' dan in de vorm van een 'tekst' i.p.v. een 'getal' of iets dergelijks.

RobIII schreef op vrijdag 10 april 2020 @ 16:59:
Als unittests érgens niet geschikt voor zijn en als je iets niet wil is 't random dingen; een unittest moet reproduceerbaar zijn, élke keer dat je 'm runt moet je dezelfde waardes zien. Anders krijg je een unittest die de ene keer passed en de andere keer failed; dat kan dus niet.

Antwoord:
Daar heb je zeker gelijk in, randomness zou je bij unit testen zeker willen vermijden. Maar ik dacht ik ga het eens proberen om te kijken of ik uit de gegenereerde string een dubbele waarde kan vinden en dat deed ik met de volgende code:

C#:

// Arrange
string generatedId = new TestClass().GenerateTransactionId();
bool found = false, expected = false;
int expectedLength = 7;
int actualLength = generatedId.Length;

// Act
for (int i = 0; i < generatedId.Length - 1; i++)
{
    // char a becomes array[index]
    char a = generatedId[i];
    // char b becomes array[index + 1]
    char b = generatedId[i + 1];

    // If there are duplicate characters, go out of the loop and stop. 
    if (a == b)
    {
        found = true;
        break;
    }
}

// Assert
// If this is not true, then duplicate characters next each other are found.
Assert.IsTrue(found == expected);
// Just to make sure: expected length is 7. 
Assert.AreEqual(expectedLength, actualLength);

RobIII schreef op vrijdag 10 april 2020 @ 18:43:
Ik heb zo m'n twijfels bij dit topic. Waarom zou in een transactie-id een letter niet herhaald mogen worden?

Antwoord:
Het was meer om te oefenen van hoe je dat kon bereiken, dus wilde ik mezelf uitdagen hoe ik dit kon bereiken.

RobIII schreef op vrijdag 10 april 2020 @ 18:43:
En waarom beperk je een transactie-id tot (minder dan) 26⁷ ≈ 34 bits? Dat geeft een enorme kans op collisions als je een beetje flink transactie-id's gaat genereren (de kans nadert 100% bij 1 miljoen transacties, of 50% vanaf zo'n 220.000 transacties en nog steeds 1% bij 27.000 transacties). En dan tel ik de beperking dat een letter niet herhaald mag worden nog niet eens mee - dat maakt 't alleen maar erger.

Antwoord:
Hoe kom je trouwens op 26? Wat adviseer je als norm, tot hoeveel bits of lengte?

RobIII schreef op vrijdag 10 april 2020 @ 18:43:
Waarom wordt er geen (G/U)UID gebruikt of, als lengte en leesbaarheid een eis zijn een ULID?

Antwoord:
Hier had ik niet aangedacht, wist niet eens dat het bestond. Waarom geef je dit als voorbeeld, wordt het door heel veel mensen gebruikt bij het willekeurig genereren van waardes?

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Gropah schreef op vrijdag 10 april 2020 @ 17:00:
- Waarom is je algoritme te lang?
- Wat is het doel van deze code? Wil je begrijpelijke code? Snelle code? Wil je leren hoe je kan optimaliseren? En op welk gebied wil je optimaliseren?

Antwoord:
Waarom?
normaliter is de code beter te onderhouden als een methode niet te lang is zoals max. 15 regels of zo of zelfs minder, daarom vond ik de methode te lang.

Doel?
Inderdaad, ik wil graag leren optimaliseren en een algoritme schrijven dat ervoor zorgt in een mum van tijd en met beperkte resources (geheugen) om bijvoorbeeld op een efficiënte wijze iets te genereren. Daarnaast moet het ook begrijpelijk zijn voor een andere programmeur.

Gropah schreef op vrijdag 10 april 2020 @ 17:00:
- Waarom pre-alloceer je niet de ruimte gezien je toch weet hoe lang je string gaat worden?
- Waarom is de maxLength afhankelijk van het aantal in de array nummers? Je hebt het er over dat de ID standaard 7 tekens lang is.
- Je slaat nogal wat dingen op als fields die niet per se in een field zouden moeten hoeven. Als de gegenereerde ID niet gecached hoeft te worden hoeft dat niet daar, idem voor random. Waarom doe je dit?

Antwoord:
Pre-allocation
Nu ik hierover nadenk, is het op zich wel een goed idee om dit toepassen inderdaad.

maxLength
Ook hiervoor geldt dat ik het alvast kan invullen, bedankt voor de tip (Ook bedankt @Philip Ross ).

Opslaan als fields
Weet je voor random, als voorbeeld, dacht ik het gewoon alvast bovenaan neer te zetten bij de andere fields, verder had ik daar niet echt over nagedacht. Welke zijn volgens jou eigenlijk niet nodig? Bedoelde je meer van, de fields zouden eigenlijk meer passen in de methode zelf, of?

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

DataGhost schreef op vrijdag 10 april 2020 @ 17:31:
Heel leesbaar is je code niet, dat er code staat is duidelijk maar wat je met die code bedoelt (en dat hoeft niet hetzelfde te zijn) is dat niet. Kan je het misschien voorzien van commentaar met daarin je gedachtengang per blokje, en de betekenis/bedoeling van je variabelen? Dan kunnen wij makkelijker beoordelen of je schrijft wat je bedoelt, en of je denkwijze een beetje logisch is.

Antwoord:
Mijn excuses, ik zal even het algoritme verduidelijken met mijn gedachtegang en waarom ik bepaalde keuzes heb gemaakt.

C#:

public string GenerateTransactionId()
{
    randomNum = new Random();
    for (int i = 0; i < maxLength; i++)
    {
        // Set the current index
        index = i;
        // Generate new integer, this will be used as char for the next index
        indexNew = randomNum.Next(0, alphabetLowChars.Count());

        char selectedChar = alphabetLowChars[indexNew];

        // Without code below, the code fails (result in first place is empty, so there are no indexes and the program fails)
        if (result == "")
            result = selectedChar.ToString();

        // The OutOfRangeException will be thrown for the 1st iteration at this line, if the result is empty. 
        char currentChar = result[index];

        // At the first iteration, these characters will always be the same (because of what I did above and I needed to do that)
        // the result was empty, therefore that had to be done. 
        if (currentChar == selectedChar)
        {
                do
                {
                    // Generate new random number as long as the first index and the next are the same
                    int tmpNewIndex = randomNum.Next(0, alphabetLowChars.Count());
                    // Add the new character next to the existing character
                    result += alphabetLowChars[tmpNewIndex];
                  // If the 1st and the 2nd character are same, go back to the beginning of the do-while loop and start over, else
                  // break this process.
                } while (result[index].Equals(result[index + 1]));
        }
        
        // Let say the if-statement with condition 'currentChar == selectedChar' became false, then that step will be skipped.
        // Imagine result.Length is 2 en i is 1 -> condition: (2 - 1 =) 1 < (result.Length =) 2 becomes true and there will be extra 
                // character added to it. I need to do this, because otherwise it will just always add an extra character and by doing this check 
                // with this condition I know there is place left to add another character and thus I achieve the desired result. This step will only 
                // be skipped, when the program went into the do-while loop, then automatically, there will no room for an extra character. 
        if ((result.Length - i) < result.Length)
                // With condition below, I make sure to skip adding another extra character when the desired length is achieved.
                if(result.Length <= maxLength)
                    result += alphabetLowChars[indexNew];
    }

    return result;
}

[edeboeck]

umask schreef op vrijdag 10 april 2020 @ 20:31:
[...]
Antwoord:
Hoe kom je trouwens op 26? Wat adviseer je als norm, tot hoeveel bits of lengte?
[...]

Er zijn 26 mogelijkheden ('a'-'z') waaruit gekozen wordt; verheffen tot de 7de macht omdat je 7 keer een keuze maakt (strikt genomen is het 26 x 25⁶ omdat het teken vanaf de tweede plaats nooit hetzelfde mag zijn als de voorganger, maar ruwweg zit dat wel in dezelfde grootteorde).

[RobIII]

DataGhost schreef op vrijdag 10 april 2020 @ 19:12:
Ik stel me altijd voor dat het iets is als floor((randomBits(X) / ((1<<X)-1)) * (upper-lower)) + lower

Tenzij je precies op bit-boundaries werkt (1, 2, 4, 8, 16, 32...), en dat is 1..26 ('a-z') dus niet, introduceer je altijd een bias en een goeie manier om daar van af te komen is ongewenste getallen dan te negeren. Dat kost je wat meer CPU cycles en, ja, je hebt een theoretische kans op een oneindige lus maar die kans is verwaarloosbaar.

umask schreef op vrijdag 10 april 2020 @ 20:31:
Antwoord:
het doel is om de string te gebruiken als een 'unieke id' dan in de vorm van een 'tekst' i.p.v. een 'getal' of iets dergelijks.

Waarom doe je dan, bijvoorbeeld, geen simpele Base26 op een (incrementeel) getal?

umask schreef op vrijdag 10 april 2020 @ 20:31:

Antwoord:
Daar heb je zeker gelijk in, randomness zou je bij unit testen zeker willen vermijden. Maar ik dacht ik ga het eens proberen om te kijken of ik uit de gegenereerde string een dubbele waarde kan vinden en dat deed ik met de volgende code:

Ja, prima, je test daar of er herhalende karakters in zitten, maar één van je belangrijkste eisen is / lijkt me toch wel dat een transaction ID "historisch" uniek is. Eerst heb je er 0 en is de kans op duplicaten dus 0. Dan heb je er 1 en is de kans op een duplicaat 1:X. Dan heb je er 2 en is de kans op een duplicaat 2:X... en zo door. En dan komt het birthday problem al heel snel om de hoek kijken.

En om dat te demonstreren:

C#:

var generatedids = new HashSet<string>();
for (int i = 0; i < 1000000; i++)
{
    var id = GenerateTransactionId();
    if (generatedids.Contains(id))
        throw new Exception($"Duplicate found in {i} iterations!");
    generatedids.Add(id);
}

Als ik die code vervolgens 10 keer draai krijg ik:

Duplicate found in 190420 iterations!
Duplicate found in 127301 iterations!
Duplicate found in 153321 iterations!
Duplicate found in 92531 iterations!
Duplicate found in 40246 iterations!
Duplicate found in 69298 iterations!
Duplicate found in 40758 iterations!
Duplicate found in 125142 iterations!
Duplicate found in 52707 iterations!
Duplicate found in 123667 iterations!

Ofwel, best case kwam ik tot 190.420 transactie-id's voordat ik op een collision stuitte (met mijn GenerateTransactionId() methode). Worst case (op 10 runs dus) al na 40.246 iteraties.

Zelfs de simpelste oplossing (gewoon een incremental ID; aaaaaaa, aaaaaab, aaaaaac, ...) lost dat al op en geeft je gegarandeerd (om-en-nabij) 26⁷ (+/- 8 miljard) unieke transactie ID's voordat er een collision optreedt - en die is ook nog eens supermakkelijk én goedkoop te vinden / detecteren want 't is precies op 't moment dat je transactionid 'overflowed' van zzzzzzz naar de volgende waarde (in jouw geval dus aaaaaaa). Waarom dan in hemelsnaam nog moeilijk doen met random letters? Haal daar desnoods nog de (nog steeds vreemde) eis dat er geen achtereenvolgende letters in moeten zitten af en dan hou je nog steeds ruimschoots meer over dan de nu, in je huidige opzet, best-case random transactie ID's.

umask schreef op vrijdag 10 april 2020 @ 20:31:
Antwoord:
Hoe kom je trouwens op 26? Wat adviseer je als norm, tot hoeveel bits of lengte?

Zie edeboeck in "Algoritme: genereren van een unieke string"

umask schreef op vrijdag 10 april 2020 @ 20:31:
Antwoord:
Hier had ik niet aangedacht, wist niet eens dat het bestond.

Een (G/U)UID is 128 bits en niet te representeren in 7 tekens a-z. En dat pas dus niet in je initiële eisen. Wat je zou kunnen doen is een (G/U)UID nemen en daar +/- 35 bits van gebruiken om je eigen ID uit te destilleren, maar where's the fun in that?

umask schreef op vrijdag 10 april 2020 @ 20:31:
Waarom geef je dit als voorbeeld, wordt het door heel veel mensen gebruikt bij het willekeurig genereren van waardes?

Een (G/U)UID is géén 'random number'! Afhankelijk van de implementatie / versie kan een (G/U)UID zelfs ontzettend voorspelbaar zijn. V4 komt dan nog 't dichtst in de buurt met 124 random bits. Maar (G/U)UID's zijn alomtegenwoordig dus, ja, het "wordt door heel veel mensen gebruikt". En (G/U)UID's worden dus vooral ingezet als unieke identifier ja. Globally of Universally zelfs, het is zelfs het eerste woord in de naam

umask schreef op vrijdag 10 april 2020 @ 20:31:
Antwoord:
Waarom?
normaliter is de code beter te onderhouden als een methode niet te lang is zoals max. 15 regels of zo of zelfs minder, daarom vond ik de methode te lang.

Ik ben 't, doorgaans, eens dat een methode niet veel meer dan 'een pagina lang' of 'wat er op je scherm past lang' moet zijn. Langere methodes wijzen vaak (uitzonderingen daargelaten) op slechte of minder optimale code. Maar wat let je om je methode op te splitsen in een aantal methodes en daarmee a) verantwoordelijkheden duidelijker af te bakenen en b) je code leesbaarder te maken?

C#:

public string GenerateTransactionId() {
  GenerateString();
  DoSomething();
  CheckSomething();
}

Elk van die methods an-sich kan dan weer "een pagina" lang zijn, maar maakt je code dus wel veel leesbaarder en maakt verantwoordelijkheden stukken duidelijker.

umask schreef op vrijdag 10 april 2020 @ 20:31:
Opslaan als fields
Weet je voor random, als voorbeeld, dacht ik het gewoon alvast bovenaan neer te zetten bij de andere fields, verder had ik daar niet echt over nagedacht. Welke zijn volgens jou eigenlijk niet nodig? Bedoelde je meer van, de fields zouden eigenlijk meer passen in de methode zelf, of?

Je moet de scope van variabelen altijd zoveel mogelijk beperken; dus uitgangspunt is lokaal in de method* en dan, waar nodig, de scope vergroten naar instance field etc. Dus pas wanneer 't nodig is "til" je een variabele "uit" je method aan vergroot je de scope. Wat jij nu doet (instance fields) maken is de omgekeerde wereld en zorgt voor allerlei problemen zoals vervuiling van de (instance) scope, bugs doordat iedere member van je instance aan die variabelen/fields kan rommelen etc. etc.

* Of zelfs nog kleiner, zoals de indexer van een for-loop vaak is bijvoorbeeld; die kun je alleen in de for-loop gebruiken.

---

Een probleem van een totaal andere categorie is dat je transaction ID's dus ook 'kutshit' en 'fuckyou' kunnen zijn. Geen idee of je gebruikers die transaction ID's ooit ergens gaan zien, maar wel even het overwegen waard. Er zijn nogal wat woorden en combinaties mogelijk met 7 letters namelijk

De vraag die bij mij nu 't meest brandt is: heb je na 't lezen van de reacties hier nog steeds de eis dat een letter niet twee keer achter elkaar mag voorkomen in het TransactionID (en zo ja: why??) of misschien dat je de eis voor 7 karakters wil heroverwegen...

[ Voor 33% gewijzigd door RobIII op 10-04-2020 22:31 ]

[DataGhost]

umask schreef op vrijdag 10 april 2020 @ 20:31:

[...]


Antwoord:
Mijn excuses, ik zal even het algoritme verduidelijken met mijn gedachtegang en waarom ik bepaalde keuzes heb gemaakt.

..code..

Ik heb even je code buiten de quote gehaald om erop te reageren.

C#:

public string GenerateTransactionId()
{
    randomNum = new Random();
    // Hier, dus niet hierboven

Bij "Hier" gaat mogelijk iets interessants mis, of beter gezegd, vergeet je iets te doen. Doe voor de gein eens

C#:

TestClass tc = new TestClass();
for(int test=0; test<1000; test++) {
    Console.WriteLine(tc.GenerateTransactionId());
}

Is dat de bedoeling? Want je code gaat namelijk wel elke keer aan de slag om uiteindelijk niks te doen of soms toch wel.

C#:

    for (int i = 0; i < maxLength; i++)
    {
        // Get the current index
        index = i;
        // Generate new integer, this will be used as char for the next index
        indexNew = randomNum.Next(0, alphabetLowChars.Count());

Je zegt het al in je code, index = i en die verandert verder niet in de loop. Waarom gebruik je dan toch die variable? Zeker als je kijkt naar de variabelenaam indexNew die niet over de index in je TID gaat maar bedoeld is voor je array met letters, is dat verwarrend.

C#:

        char selectedChar = alphabetLowChars[indexNew];

        // Without code below, the code fails (result in first place is empty, so there are no indexes and the program fails)
        if (result == "")
            result = selectedChar.ToString();

        // The OutOfRangeException will be thrown for the 1st iteration at this line, if the result is empty. 
        char currentChar = result[index];

        // At the first iteration, these characters will always be the same (because of what I did above and I needed to do that)
        // the result was empty, therefore that had to be done. 
        if (currentChar == selectedChar)
        {

Je hebt hier al door dat je eigenlijk altijd een eerste teken in je TID wilt hebben voordat je dingen kan vergelijken. Is het dan niet handig om dat buiten de loop al te doen bijvoorbeeld? Dan hoef je daar binnen de loop geen rekening meer mee te houden.

C#:

                do
                {
                    // Generate new random number as long as the first index and the next are the same
                    int tmpNewIndex = randomNum.Next(0, alphabetLowChars.Count());
                    // Add the new character next to the existing character
                    result += alphabetLowChars[tmpNewIndex];
                  // If this the 1st and the 2nd character are same, go back to the beginning of the do-while loop and start over, else
                  // break this process.
                } while (result[index].Equals(result[index + 1]));

Buiten dat dit (als je creatief nadenkt maar daar kan ik je later wel een hint voor geven) zonder loop kan, gaat hier in ieder geval iets mis. Doe eens iets als

C#:

for(int test=0; test<1000; test++) {
    Console.WriteLine(new TestClass().GenerateTransactionId());
}
// of liever, als je inderdaad iets hebt aangepast nav mijn eerste blokje:
TestClass tc = new TestClass();
for(int test=0; test<1000; test++) {
    Console.WriteLine(tc.GenerateTransactionId());
}

Dat zou alsnog ruim binnen een seconde klaar moeten zijn maar waarschijnlijk loopt 'ie op een gegeven moment vast. Zeker unittests over random dingen die aan bepaalde eisen moeten voldoen, voor zover nuttig, zou je liefst minimaal duizenden keren moeten runnen. Dan weet je nog steeds niet of je code correct is, maar de kans op het vinden van een fout wordt groter.
Daarnaast zorgt dit ervoor dat je in de eerste iteratie van je loop (i=0) altijd twee letters van je TID genereert, volgens mij bedoel je dat niet.

C#:

        }
        
        // Let say the if-statement with condition 'currentChar == selectedChar' became false, then that step will be skipped.
        // Imagine result.Length is 2 en i is 1 -> condition: (2 - 1 =) 1 < (result.Length =) 2 becomes true and there will be extra 
                // character added to it. I need to do this, because otherwise it will just always add an extra character and by doing this check 
                // with this condition I know there is place left to add another character and thus I achieve the desired result. This step will only 
                // be skipped, when the program went into the do-while loop, then automatically, there will no room for an extra character. 
        if ((result.Length - i) < result.Length)
                // With condition below, I make sure to skip adding another extra character when the desired length is achieved.
                if(result.Length <= maxLength)
                    result += alphabetLowChars[indexNew];
    }

Hier gebruik je dan opeens i in plaats van index. Maar ik vond je guard interessanter. Schrijf het eens puur wiskundig op: a - i < a, en vereenvoudig dat dan. De momenten waarop dat waar is is onafhankelijk van a, dus dit maakt het niet direct leesbaarder. Ik kwam uit op i > 0 en volgens mij doet dat niet wat je wilt. Print eens een hele stapel van je gegenereerde TIDs? Ik denk dat je er veel zult krijgen met een vorm als abcbdef, of in ieder geval bovengemiddeld veel voorkomens van drie opeenvolgende letters met de vorm xyx, vanaf de tweede positie in result. Dat kan natuurlijk lastig te zien zijn in de output dus probeer je code eens na te lopen en te zien in welke gevallen dit kan gebeuren.
Verder is het eigenlijk een hele hoop wol om selectedChar toe te voegen aan je result als die niet hetzelfde is als currentChar hint hint, dus daar had je een andere, veel simpelere constructie voor kunnen gebruiken. Dit had ik daarnet voordat ik ging eten al door, terwijl ik dit begon te typen was ik het alweer vergeten en moest ik nog eens goed door heel je functie heen pluizen om te zien waar het ook alweer goed voor was. Dat is dus niet superduidelijk.
Ook denk ik dat het mogelijk is om er TIDs van 8 tekens lang uit te krijgen, maar de laatste drie tekens zullen dan in zo'n 50% van de gevallen weer van de vorm xyx zijn. Nog langere zijn ook nog mogelijk, maar de kans daarop is echt behoorlijk klein.

Ten slotte mag je dit natuurlijk schrijven zonder { } maar voor de leesbaarheid en onderhoudbaarheid zou ik je willen aanraden aan te leren die altijd gebruiken. Als je een keer niet goed kijkt en "in de body" een extra regel neer wilt zetten kan je een leuke verrassing krijgen:

C#:

if(a)
    b();
    c();

doet iets heel anders dan

C#:

if(a) {
    b();
    c();
}

Oja en last but not least:

C#:

    return result;
}

Niks op aan te merken. Top!

Disclaimer verder: ik heb niks van de code uitgevoerd en gebruik verder geen C#. Alles heb ik uit m'n hoofd beredeneerd dus het kan best fout zijn.
Tussendoor-edit: ik heb de code nu wel even in Python geschreven en uitgevoerd met twee simpele fixes die ik hierboven gesuggereerd had. Ik krijg in ieder geval resultaten als

code:

qpdpmpv
yojogisr
jxlxrgkf
zkzwzbr
rxvxwny
wuwuhbdc
dpjpcjkho
ikdklckit
lgkguagvd
rwuwxpwci
mpxpwxhxc
gcsisliin

Drie daarvan zijn "correct" maar wellicht ongewenst, drie daarvan zijn gewoon te lang en komen best vaak voor. De laatste zes komen echt bijna nauwelijks voor, uit 10 miljoen runs kreeg ik er 61 van die lengte. Daar moet je dus ontzettend vaak voor testen! Heel interessant zijn trouwens de laatste drie tekens van de laatste in deze lijst
Deze kwamen ook nog langs, voordat ik een van de hierboven gesuggereerde dingen gefixt had:

code:

sjqcpzpipw
lqcnmtnpc
lqcnmtnpce
wukyxpjipcfjpj
wukyxpjipcfjpjs
uqdhdztebtnfouuntumwsefqfjbuzvrzpwsrbyefdcmbmrwipjpiyibgufjikvqtplifovxxvognccwwydugagbhqbdwqbbyznsjl
uqdhdztebtnfouuntumwsefqfjbuzvrzpwsrbyefdcmbmrwipjpiyibgufjikvqtplifovxxvognccwwydugagbhqbdwqbbyznsjlnw
uqdhdztebtnfouuntumwsefqfjbuzvrzpwsrbyefdcmbmrwipjpiyibgufjikvqtplifovxxvognccwwydugagbhqbdwqbbyznsjlnwu
uqdhdztebtnfouuntumwsefqfjbuzvrzpwsrbyefdcmbmrwipjpiyibgufjikvqtplifovxxvognccwwydugagbhqbdwqbbyznsjlnwul
uqdhdztebtnfouuntumwsefqfjbuzvrzpwsrbyefdcmbmrwipjpiyibgufjikvqtplifovxxvognccwwydugagbhqbdwqbbyznsjlnwulb

en dat is afhankelijk van hoe je je code gebruikt of echt enorm onwenselijk of een situatie die niet voor gaat komen.

RobIII schreef op vrijdag 10 april 2020 @ 21:25:
[...]

Tenzij je precies op bit-boundaries werkt (1, 2, 4, 8, 16, 32...), en dat is 1..26 ('a-z') dus niet, introduceer je altijd een bias en een goeie manier om daar van af te komen is ongewenste getallen dan te negeren. Dat kost je wat meer CPU cycles en, ja, je hebt een theoretische kans op een oneindige lus maar die kans is verwaarloosbaar.

Ah, natuurlijk, dat had ik even over het hoofd gezien. Ik haalde wiskunde en informatica door elkaar en ging even uit van dat een double net zo precies was als een reëel getal Maar eigenlijk zat ik dus teveel te denken aan het genereren van een letter zonder duplicaten, wat zonder duplicaten negeren mogelijk is, en reageerde daarom dus onterecht op jouw code. Ik gebruik hier zelf zoveel mogelijk library-functies voor, waarbij ik controleer dat die intern een goede uniforme (of andere gewenste) verdeling gebruikt.

[ Voor 9% gewijzigd door DataGhost op 10-04-2020 22:56 ]

[P-Storm]

Ook nog 2 cents van mij: Indien je de c# Pseudorandom wilt gebruiken (new Random) dan zou ik dit lezen: Avoiding Multiple Instances.

Maar beter is om wat ook @RobIII aangeeft, maak gebruik van de RNGCryptoServiceProvider.

[zoxzo]

Nog wat centen:
Allereerst, je kan ook meteen indices vergelijken in plaats van de daardoor geselecteerde characters.

Misschien inmiddels overbodig, maar neem een stap terug en bekijk het probleem nogmaals. Dan zie ik tenminste drie verschillende benaderingen:

1. De jouwe, dwz een loop waarin er steeds een extra random character aangemaakt en getest wordt totdat dat character voldoet.
2. Eentje, waarbij het probleem opsplitst wordt in twee onafhankelijke stukken:
   1. Genereer een string van 7 random characters
   2. Test of deze hele string voldoet
      (in C++ kan je daarvoor de standaard functie "adjacent_find" voor gebruiken, geen idee of C# ook zoiets kent).
   Met als voordelen dat toekomstige veranderingen in de eisen makkelijker door te voeren zijn en dat ieder stuk ook los te testen is.
3. Daarnaast bestaat er ook nog een manier om te zorgen dat elk aan te maken character meteen voldoet, waarbij dus de hele test achteraf overbodig is. Denk hier eerst maar eens over na.

[epic007]

Even los van de discussie over de eisen aan het transactionid en welke random functie te gebruiken vond ik het wel een leuke uitdaging om een kortere versie te schrijven (corona verveling)

Ik kwam op 16 regels, krijgt iemand hem korter?

C#:

public class Program
{
    public static void Main()
    {
        var x = 100;
        while (x-- > 0)
        {
            Console.WriteLine(Generate());          
        }
    }
    
    private static Random rnd = new Random();
    
    private static char[] alphabet = new char[]
    {
        'a','b','c','d','e','f','g','h','i','j','k','l','m',
        'n','o','p','q','r','s','t','u','v','w','x','y','z'
    };
    
    public static string Generate(int length = 7)
    {       
        var prev = '#'; // initialize with non-possible char
        var count = 0;
        var result = new char[length];
        while (count < length) 
        {
            var idx = rnd.Next(alphabet.Length);
            var next = alphabet[idx];
            if (prev != next) 
            {
                result[count++] = next;
                prev = next;
            }
        }   
        return new string(result);
    }
}

https://dotnetfiddle.net/X6XOw5

[RobIII]

epic007 schreef op dinsdag 14 april 2020 @ 09:09:
Ik kwam op 16 regels, krijgt iemand hem korter?

How about 1 regel Geen opeenvolgende duplicaat karakters, wel bias, wel de totale space gehalveerd

(En jij telt voor 't gemak de "2" regels die je nodig hebt buiten je functie voor de rng en alphabet niet mee )

Also: 1 regel, wél opeenvolgende duplicaat karakters (wat nog steeds een rare eis is), wel bias, totale space bruikbaar.

Also: 17 regels zonder te 'minimizen' c.q. "leesbare" code*, geen opeenvolgende duplicaat karakters, geen bias, totale space bruikbaar, CSRNG (en iets mooier in C# 8 met de ^1 index operator).

* Comments zijn met opzet achterwege gelaten; oefening voor de lezer

[ Voor 76% gewijzigd door RobIII op 14-04-2020 16:10 ]

[DataGhost]

epic007 schreef op dinsdag 14 april 2020 @ 09:09:
Even los van de discussie over de eisen aan het transactionid en welke random functie te gebruiken vond ik het wel een leuke uitdaging om een kortere versie te schrijven (corona verveling)

Ik kwam op 16 regels, krijgt iemand hem korter?

Ik vind het aantal regels geen boeiende metric, o.a. omdat je in C# en aanverwante talen gewoon alles op 1 regel kan zetten. Uitdagender (maar ook niet supermoeilijk) is om het in O(length) te doen, dat is jouw oplossing niet Zonder bias kan dat ook, mijn oplossing in Python doet dat in 9 regels en je kan het met wat schuiven veranderen in 6 regels.

RobIII schreef op dinsdag 14 april 2020 @ 09:58:
[...]
totale space (-1) bruikbaar (eerste karakter zal nooit een 'z' zijn)

Nja heel moeilijk is dat toch niet te vermijden?

[ Voor 17% gewijzigd door DataGhost op 14-04-2020 14:39 ]

[RobIII]

Ik zou nu wel graag van @umask eens willen horen:

1. Vanwaar de eis voor geen herhalende karakters
2. Waarom er gekozen is voor random transactie ID's i.p.v. incrementele bijv.
3. Waarom er gekozen is voor maar 7 tekens voor 't transactie ID (zie vorige vraag; kans op collisions is huge)
4. Waar dit voor bedoeld is / wat het nut is. Is het een educatief iets of gaat dit in productie gebruikt worden?

DataGhost schreef op dinsdag 14 april 2020 @ 12:35:
Nja heel moeilijk is dat toch niet te vermijden?

It is. Fixed

DataGhost schreef op dinsdag 14 april 2020 @ 12:35:
Zonder bias kan dat ook

Geeft randrange een unbiased output? (Edit: Vanaf 3.2 apparently )
Waarom doe jij een >= op line 10 ipv ==?

[ Voor 75% gewijzigd door RobIII op 14-04-2020 16:00 ]

[DataGhost]

RobIII schreef op dinsdag 14 april 2020 @ 14:18:
Geeft randrange een unbiased output? (Edit: Vanaf 3.2 apparently )

Yes, natuurlijk gecheckt in de docs

Waarom doe jij een >= op line 10 ipv ==?

Om een ander soort bias te voorkomen. Heeft met regel 9 (vs 6) te maken.

[ Voor 13% gewijzigd door DataGhost op 14-04-2020 16:26 ]

[umask]

RobIII schreef op dinsdag 14 april 2020 @ 14:18:
Ik zou nu wel graag van @umask eens willen horen:

• Vanwaar de eis voor geen herhalende karakters
• Antwoord: Ik wilde mezelf 'puur' uitdagen, that's all. (ik snap dat het niet slim is ivm collisions..)
• Waarom er gekozen is voor random transactie ID's i.p.v. incrementele bijv.
• Antwoord: Nou ja, ik vind dat een 'transactieId' net zoals op een bon (bijv. van een supermarkt die je krijgt, nadat je hebt betaald) ook een willekeurige -> unieke Id staat vermeld. Ook in dit geval vind ik dus dat het een unieke string moet zijn i.p.v. een incrementele cijfer..
• Waarom er gekozen is voor maar 7 tekens voor 't transactie ID (zie vorige vraag; kans op collisions is huge)
• Antwoord: het is maar een willekeurig getal.. het kon net zo goed ook 10 zijn bij wijze van spreken.
• Waar dit voor bedoeld is / wat het nut is. Is het een educatief iets of gaat dit in productie gebruikt worden?
• Antwoord: het is voor mijn eigen ontwikkeling, dus je kunt het wel 'educatief' noemen inderdaad.

[umask]

zoxzo schreef op maandag 13 april 2020 @ 17:54:
Nog wat centen:

• #1 Allereerst, je kan ook meteen indices vergelijken in plaats van de daardoor geselecteerde characters.
• #2 Daarnaast bestaat er ook nog een manier om te zorgen dat elk aan te maken character meteen voldoet, waarbij dus de hele test achteraf overbodig is. Denk hier eerst maar eens over na.

Zou je misschien van #1 en #2 voorbeelden kunnen noemen/dit kunnen toelichten (je hoeft het antwoord niet voor te leggen), maar zodat ik een beetje de juiste kant op kan gaan en niet helemaal afwijk..

[RobIII]

umask schreef op dinsdag 14 april 2020 @ 18:12:
Antwoord: Nou ja, ik vind dat een 'transactieId' net zoals op een bon (bijv. van een supermarkt die je krijgt, nadat je hebt betaald) ook een willekeurige -> unieke Id staat vermeld.

Ik denk dat die minder random is dan je denkt
Als je bekend bent met, zeg, Base32, Base64 en consorten; dan zou je je ID kunnen encoden (en ook weer decoden). Maar dat zie je dan nog steeds vrij 'incrementeel' oplopen (...aaa -> aab). Maar net zoals jij een alphabetLowChars gebruikt waar je braaf het alfabet in zet... hussel dat alfabet eens? Dan kun je nog steeds encoden/decoden (mits je altijd diezelfde gehusselde volgorde gebruikte uiteraard). Dan heb je een 'random'(-iger) alfanumeriek ID. Het is niet super-sterk (na een paar bonnetjes heb je waarschijnlijk wel de volgorde in de gaten) maar het gaat om 't idee (of ID ). Daarbij: incrementeel hoeft niet altijd +1 te betekenen he? +42 is ook incrementeel.

En anders moet je eens kijken naar (G/U)UID's / ULID's zoals al eerder aangegeven of naar iets als dit (disclaimer: auteur). Of zoals een gfycat 't doet bijvoorbeeld; die gebruiken woorden ipv letters. En anders kun je, zolang je zorgt dat je geen collisions krijgt, met wat slim bitschuiven je ID ook minder incrementeel laten lijken; dat weer encoden met een 'geshuffeld alfabet' en dan moet iemand al echt z'n tanden erin zetten willen ze je id kunnen 'decoden' (let wel: beschouw je ID wel als gewoon openbaar; het is géén encryptie o.i.d). Hoe dan ook: Er zijn talloze manieren.

umask schreef op dinsdag 14 april 2020 @ 18:15:
Zou je misschien van #1 en #2 voorbeelden kunnen noemen/dit kunnen toelichten (je hoeft het antwoord niet voor te leggen), maar zodat ik een beetje de juiste kant op kan gaan en niet helemaal afwijk..

#1: Een string is eigenlijk een char-array dus je kunt gewoon mystring[42] doen.
#2: Wat @DataGhost en ik in grote lijnen doen: Pak een willekeurige getal tussen 0 en 25. Dat is je eerste a-z letter (waarbij 0 -> a en 25 -> z). Daarna pak je telkens een getal tussen 1 en 25 en die tel je bij de vorige letter op (stel je had d en nu heb je 2 dan krijg je dus d + 2 = f wordt je volgende letter). Omdat je nooit 0 genereert heb je dus nooit dezelfde letter achter elkaar; hou er welk rekening mee dat je modulo 26 moet doen om een 'overflow' van je alfabet te 'wrappen' naar het begin van je alfabet.

[ Voor 41% gewijzigd door RobIII op 14-04-2020 18:53 ]

[umask]

RobIII schreef op dinsdag 14 april 2020 @ 18:24:
[...]

Hmm, bedankt je voor je uitleg. Ik zal eens gaan kijken naar die voorbeelden die jullie hebben gegeven. Daarnaast wacht ik ook een beetje af, misschien komen nog andere mensen op goede ideeën, wie weet.

[RobIII]

umask schreef op dinsdag 14 april 2020 @ 18:37:
misschien komen nog andere mensen op goede ideeën, wie weet.

Naar wélke goede ideeën ben je dan (nog) naar op zoek? Het is mij niet duidelijk wat je nu nog wil: binnen je zelf opgelegde beperkingen blijven (7 karakters, geen herhaling, random) of ...? De belangrijke(re) vragen: waar ga je dat ID genereren: heb jij één instantie die dat ID uitdeelt? Of ga je dat op verschillende hosts of in verschillende threads doen? Ofwel: coordinated/uncoordinated distributed, of toch meer single instance? En heb je al stilgestaan wat een random ID doet met indexen/pages van je RDBMS (if any)? En hoe je zo'n ID gaat representeren in je RDBMS? Varchar? Byte-array _{waarbij de string die we nu in dit topic genereren de human-readable representatie ervan is}? Blob?

Ik snap dat 't gewoon voor de lol / leermoment is, maar ik mis vooral (behalve dus een paar 'vreemde' beperkingen) de duidelijke afkadering van de eisen en 't uiteindelijke doel.

[ Voor 49% gewijzigd door RobIII op 14-04-2020 19:01 ]

[umask]

RobIII schreef op dinsdag 14 april 2020 @ 18:50:

Naar wélke goede ideeën ben je dan (nog) naar op zoek? Het is mij niet duidelijk wat je nu nog wil: binnen je zelf opgelegde beperkingen blijven (7 karakters, geen herhaling, random) of ...?

De belangrijke(re) vragen: waar ga je dat ID genereren: heb jij één instantie die dat ID uitdeelt? Of ga je dat op verschillende hosts of in verschillende threads doen? Ofwel: coordinated/uncoordinated distributed, of toch meer single instance?

Antwoord: ik had meer in gedachte dat het door meerdere instanties gedaan kan worden, aangezien ik meerdere keren een instantie ervan wil kunnen aanmaken en toedelen van een transactionId..

RobIII schreef op dinsdag 14 april 2020 @ 18:50:
En heb je al stilgestaan wat een random ID doet met indexen/pages van je RDBMS (if any)? En hoe je zo'n ID gaat representeren in je RDBMS? Varchar? Byte-array _{waarbij de string die we nu in dit topic genereren de human-readable representatie ervan is}? Blob?

Antwoord: je vraag is natuurlijk terecht, maar ik dacht meer aan de nvchar?

[RobIII]

umask schreef op dinsdag 14 april 2020 @ 21:18:
Antwoord: ik had meer in gedachte dat het door meerdere instanties gedaan kan worden, aangezien ik meerdere keren een instantie ervan wil kunnen aanmaken en toedelen van een transactionId..

Tenzij je 't bij een paar honderd transacties wil houden (met nog steeds een aardige kans op een collision) zul je dus je transaction ID moeten oprekken van 7 karakters (~33 bits) naar iets van minimaal 100nogwat bits* waardoor de kans op een collision verwaarloosbaar wordt of je zult slimmer dan 'random' een ID moeten genereren (door bijv. elke instantie een eigen 'range' te geven waaruit die ID's kan uitgeven zodat instanties elkaar niet in de weg gaan lopen. En dat is precies wat Twitter's Snowflake deed en IdGen nog steeds doet

* Wat zich in jouw 'encoding' vertaalt in 25+ a-z tekens; ik zou dus ook kijken of je niet nog de getallen 0-9 o.i.d. wil toevoegen - en dan kom je al gauw bij Base32 waarbij je precies genoeg tekens hebt om "5 hele bits" te vullen en je, als bonus, ambigu tekens als i, l, 1 en o, 0 vrij uitwisselbaar hebt. Hoe meer tekens je toestaat, hoe efficiënter je encoding.

umask schreef op dinsdag 14 april 2020 @ 21:18:
Antwoord: je vraag is natuurlijk terecht, maar ik dacht meer aan de nvchar?

Dat is vreselijk inefficiënt; je ID bestaat per letter uit max. 5 bits; dat is minimaal 3 bits per karakter overhead. Om jouw 7 a-z karakters op te slaan heb je pakweg 33 bits nodig maar je zult er minimaal 7 * 8 = 56 gebruiken ofwel een overhead van 41%. Ik bedoel; het kan hoor en bij een paar honderd of duizend records zul je er echt niet op leeglopen maar het kan allemaal veel efficiënter.

[ Voor 18% gewijzigd door RobIII op 14-04-2020 21:53 ]

[edeboeck]

RobIII schreef op dinsdag 14 april 2020 @ 21:28:
[...]
Dat is vreselijk inefficiënt; je ID bestaat per letter uit max. 5 bits; dat is minimaal 3 bits per karakter overhead. Om jouw 7 a-z karakters op te slaan heb je pakweg 33 bits nodig maar je zult er minimaal 7 * 8 = 56 gebruiken ofwel een overhead van 41%. Ik bedoel; het kan hoor en bij een paar honderd of duizend records zul je er echt niet op leeglopen maar het kan allemaal veel efficiënter.

Volgens mij zelfs 7 * 16 omdat TS nvchar voorstelt (de unicode variant) + nog de overhead voor de lengte van de string (omwille van nvchar).

@umask Als je weet dat je ID enkel uit a-z bestaat en 7 tekens lang is, neem je char(7) ... keep it simple: je gebruikt enkel waarden uit de basis ASCII-tabel (daarom geen unicode nodig) en de lengte van jouw string ligt vast (zelfs als dat niet vast zou liggen, maar b.v. allemaal tussen 8 en 10 lang, is het nog steeds interessanter om voor char(10) te gaan dan voor varchar(10)... variabele lengte wordt pas interessant bij voldoende grote verschillen).
@RobIII ik ben het met jou eens omtrent de efficiëntie, maar ik denk dat dat aspect hier minder aan de orde is, gezien de context van de vraag - daarnaast leidt het niet gebruiken van een char (of aanverwant type) automatisch tot de nood aan omzetting tussen wat opgeslagen wordt in de DB en wat wordt gebruikt in C#.

[RobIII]

edeboeck schreef op dinsdag 14 april 2020 @ 22:08:
Volgens mij zelfs 7 * 16 omdat TS nvchar voorstelt (de unicode variant) + nog de overhead voor de lengte van de string (omwille van nvchar).

Ah, ik had de n niet eens gezien Dat brengt de inefficiëntie zelfs tot 70+%

edeboeck schreef op dinsdag 14 april 2020 @ 22:08:
@RobIII ik ben het met jou eens omtrent de efficiëntie, maar ik denk dat dat aspect hier minder aan de orde is, gezien de context van de vraag - daarnaast leidt het niet gebruiken van een char (of aanverwant type) automatisch tot de nood aan omzetting tussen wat opgeslagen wordt in de DB en wat wordt gebruikt in C#.

Nee, helemaal eens, maar ik denk/vermoed/voel aan m'n water dat de string ook daadwerkelijk zo hop de DB in gaat bij TS. En of efficiëntie hier aan de orde is is, vind ik, lastig te bepalen uit de (nogal karige) context van de vraag; en dit zijn zéker wel dingen waar je bij stil wil staan als je dan toch (om welke reden dan ook) een wiel opnieuw wil uitvinden. Of je er dan iets mee doet of denkt "lekker interessant" is vers twee, maar dan heb je die keuze iig bewust gemaakt i.p.v. dat je over 5 jaar als eigenaar van FaceGramItter denkt "shit, had ik maar..." Ik wou 't alleen even op de kaart zetten / bewustwording kweken

[ Voor 3% gewijzigd door RobIII op 14-04-2020 22:16 ]

[Liveshort]

Misschien nog een leuke voor wat extra inzicht: in C en aanverwante talen zijn chars eigenlijk niet heel veel meer dan bytes. Voor Unicode etc moet je wat extra hoepels door, meen dat dat in C# hetzelfde is, maar dat het wel makkelijker is dan in C. Als je dan de ASCII tabel googelt, zul je zien dat a tot z correspondeert met nummer 97 tot 122. Deze waardes kun je direct in een char stoppen, onder de motorkap verschillen deze methode en het toewijzen van een letter tussen aanhalingstekens niet.

Het voordeel hiervan is, dat je die hele array met alfabetletters weg kunt laten en dat de vertaalslag naar een letter gewoon een optelsom is. (Sterker nog, misschien dat je wel iets als 4+'a' kan doen om 'e' te krijgen, maar dat zou je even moeten proberen.) Gecombineerd met de methode van Rob hierboven moet wel iets efficiënts te schrijven zijn.

[Rotterdammertje]

Het vermijden van opeenvolgende duplicaten is simpel. Uitgaande van een array van 26 mogelijke symbols (alle lower case letters):

1. kies de eerste index random in de range [0, 26)
2. volgende index = (vorige index + random [1, 26)) mod 26

Als de random functie een mooie uniforme verdeling geeft, dan levert dit ook een uniform verdeelde willekeurige reeks aan indices op, zonder opeenvolgende duplicaten.

[Creepy]

Liveshort schreef op woensdag 15 april 2020 @ 10:19:
Misschien nog een leuke voor wat extra inzicht: in C en aanverwante talen zijn chars eigenlijk niet heel veel meer dan bytes. Voor Unicode etc moet je wat extra hoepels door, meen dat dat in C# hetzelfde is, maar dat het wel makkelijker is dan in C. Als je dan de ASCII tabel googelt, zul je zien dat a tot z correspondeert met nummer 97 tot 122. Deze waardes kun je direct in een char stoppen, onder de motorkap verschillen deze methode en het toewijzen van een letter tussen aanhalingstekens niet.

Het voordeel hiervan is, dat je die hele array met alfabetletters weg kunt laten en dat de vertaalslag naar een letter gewoon een optelsom is. (Sterker nog, misschien dat je wel iets als 4+'a' kan doen om 'e' te krijgen, maar dat zou je even moeten proberen.) Gecombineerd met de methode van Rob hierboven moet wel iets efficiënts te schrijven zijn.

Je bedoelt zoals RobIII dat al heeft gedaan RobIII in "Algoritme: genereren van een unieke string" ?

[Liveshort]

Verdorie.

Zul je altijd zien dat er al iemand op het internet is die je voor was.

[RobIII]

Rotterdammertje schreef op woensdag 15 april 2020 @ 10:30:
Het vermijden van opeenvolgende duplicaten is simpel. Uitgaande van een array van 26 mogelijke symbols (alle lower case letters):

1. kies de eerste index random in de range [0, 26)
2. volgende index = (vorige index + random [1, 26)) mod 26

Als de random functie een mooie uniforme verdeling geeft, dan levert dit ook een uniform verdeelde willekeurige reeks aan indices op, zonder opeenvolgende duplicaten.

Je bedoelt zoals ik omschrijf in RobIII in "Algoritme: genereren van een unieke string" ?

[umask]

Rotterdammertje schreef op woensdag 15 april 2020 @ 10:30:
Het vermijden van opeenvolgende duplicaten is simpel. Uitgaande van een array van 26 mogelijke symbols (alle lower case letters):

1. kies de eerste index random in de range [0, 26)
2. volgende index = (vorige index + random [1, 26)) mod 26

Als de random functie een mooie uniforme verdeling geeft, dan levert dit ook een uniform verdeelde willekeurige reeks aan indices op, zonder opeenvolgende duplicaten.

RobIII schreef op dinsdag 14 april 2020 @ 09:58:
Also: 17 regels zonder te 'minimizen' c.q. "leesbare" code*, geen opeenvolgende duplicaat karakters, geen bias, totale space bruikbaar, CSRNG (en iets mooier in C# 8 met de ^1 index operator).

Question:
Even een vraagje, waarom moet je uiteindelijk modulo 26 doen? @RobIII of @Rotterdammertje

[RobIII]

umask schreef op zondag 19 april 2020 @ 00:32:
Question:
Even een vraagje, waarom moet je uiteindelijk modulo 26 doen? @RobIII of @Rotterdammertje

Wedervraagje: heb je al eens uitgezocht wat de modulo operator doet?

Je zult 't 't snelst zien als je een for-lus schrijft:

C#:

for (int i = 0; i < 100; i++)
  Console.WriteLine(i % 26);

Iedereen doet er kei moeilijk over (wikipedia, youtube, eerder gelinkte MSDN) maar het is gewoon de rest na deling. C'est tout. Dit heb je in groep 4 al geleerd.

Dus: 6 mod 4 = 2 (want 6 / 4 = 1 rest 2). 17 mod 6 = 5 (want 17 / 6 = 2 rest 5). Als je dit even doet zul je al gauw merken dat de uitkomst nooit hoger dan, of gelijk is aan, het modulo getal. Als je iets mod 6 doet krijg je alleen uitkomsten 0, 1, 2, 3, 4 of 5. Doe je iets mod 3 dan krijg je alleen 0, 1, 2. En met dat 'handigheidje' kun je dus super makkelijk een 'circulaire teller' maken zoals bovenstaande code toont. Al tel je tot je een ons weegt met i, je zult alleen maar 0...25 zien. En dat 'mapped' dus supermooi precies op je array bounds. Dus met de modulo operator ga je nooit buiten je array bounds maar ga je als je 't eind bereikt weer netjes naar 't begin (ofwel "wrap around").

Modulo wordt veel gebruikt in encryptie. En, toevallig, ook vaak om bijvoorbeeld random getallen binnen een bepaald bereik te houden; stel je hebt een RNG die altijd gewoon een random byte uitspuugt (0..255) maar je hebt waardes nodig tussen 0..9; dan neem je dus gewoon de output van de RNG en doe je die mod 10. Klaar! Toch? Nou... niet helemaal. Deze methode wordt vaak en veel gebruikt, maar introduceert wel een bias en dat is, coincidentally, waar 't eerder in dit topic over ging. Als je RNG (waarvan ik aanneem dat die zélf unbiased is!) waardes tussen 0 en 249 (dus een mooie ronde 250 mogelijke waardes) zou uitspugen dan was dit een perfect valide methode om getallen tussen 0..9 te genereren; immers: de kans op elk getal is immers 250/10 = 25. Maar omdat je nog 5 extra waardes hebt zullen die dus een bias geven waardoor de cijfers 0..4 dus 1/25^e vaker zullen voorkomen dan de getallen 5..9 (immers 255/10 = 25.5). Dat geeft niet als je die waardes alleen maar gebruikt om te bepalen of je spookje links of rechts moet in Pacman, of de hoogte van het gat te bepalen in Flappy Bird*, maar bouw je er een online pokertoernooi mee of gebruik je 't voor de loterij of, nog erger, in encryptie dan zul je er dus bewust van moeten zijn dat je met de modulo operator een bias introduceert. En dat is precies de reden waarom mijn 'bias-loze' voorbeelden allemaal gewoon waardes boven de 26 weggooien i.p.v. er de modulo operator op los te laten. En dat is ook de reden waarom ik alles bitwise AND met 0x1F; daarmee gooi ik de meest linkse 3 bits ("MSB's") waardoor alle uitkomsten die oorspronkelijk tussen 0..255 liggen zullen vallen tussen 0..31 zonder daar een bias te introduceren en waardoor we dus minder getallen hoeven te discarden die uit de RNG komen. Waarom je 'straffeloos' die 3 bits kunt wegmikken zonder bias te introduceren laat ik even aan jou / de lezer. Ik denk dat ik al (veel) dieper ben gegaan dan nodig

* En geloof me: échte die-hard gamers die een spel tot op 't bot kennen en daar hun leven van gemaakt hebben vinden dit soort dingen feilloos en doen daar óók hun voordeel mee. Punt is dat 't in sommige gevallen helemaal niet zo "erg" is om (een beetje) een bias te hebben.

Note trouwens dat ik nergens heb gezegd dat de Random class geen uniforme distributie geeft; volgens mij is dat wel zo. Ik koos echter voor een CSRNG (in dit geval RNGCryptoServiceProvider) omdat deze minder voorspelbaar is dan Random; dat staat (in principe) los van de distributie. En omdat de RNGCryptoServiceProvider alleen maar bytes geeft moet je dus zelf aan de slag om daar bepaalde ranges (in ons geval 0..25) uit te plukken en ben je dus zélf 'verantwoordelijk' voor 't voorkomen van die bias waar een Random.Next(0, 25) dat (mogelijk) al voor je doet.

Al-met-al dus misschien een beetje overkill, maar on the other hand: je deed 't om er iets van te leren. Now you have

[ Voor 126% gewijzigd door RobIII op 19-04-2020 12:25 ]

[Matis]

@RobIII psst, 17 mod 6 is 5. Want 17 / 6 = 2 rest 5 overigens is -17 mod 6 wel 1
Verder helemaal eens met je uiteenzetting!

[ Voor 12% gewijzigd door Matis op 19-04-2020 09:44 ]

[RayNbow]

Matis schreef op zondag 19 april 2020 @ 09:42:
overigens is -17 mod 6 wel 1

Het resultaat van de modulo-operatie is taalafhankelijk. In C# is het teken van het resultaat gelijk aan het deeltal (dus -5). In bijv. Python is het teken gelijk aan de deler (dus 1).

[RobIII]

Matis schreef op zondag 19 april 2020 @ 09:42:
@RobIII psst, 17 mod 6 is 5. Want 17 / 6 = 2 rest 5 overigens is -17 mod 6 wel 1

offtopic:
Whoopsie Er 19 had moeten staan. 19 mod 6 = 1. Maar ik heb 't aangepast.

[Matis]

RayNbow schreef op zondag 19 april 2020 @ 10:36:
Het resultaat van de modulo-operatie is taalafhankelijk. In C# is het teken van het resultaat gelijk aan het deeltal (dus -5). In bijv. Python is het teken gelijk aan de deler (dus 1).

Dat wist ik niet. Heb nooit met C# gewerkt.

[umask]

RobIII schreef op zondag 19 april 2020 @ 00:57:
Iedereen doet er kei moeilijk over (wikipedia, youtube, eerder gelinkte MSDN) maar het is gewoon de rest na deling. C'est tout. Dit heb je in groep 4 al geleerd.

Dus: 6 mod 4 = 2 (want 6 / 4 = 1 rest 2). 17 mod 6 = 5 (want 17 / 6 = 2 rest 5). Als je dit even doet zul je al gauw merken dat de uitkomst nooit hoger dan, of gelijk is aan, het modulo getal. Als je iets mod 6 doet krijg je alleen uitkomsten 0, 1, 2, 3, 4 of 5. Doe je iets mod 3 dan krijg je alleen 0, 1, 2. En met dat 'handigheidje' kun je dus super makkelijk een 'circulaire teller' maken zoals bovenstaande code toont. Al tel je tot je een ons weegt met i, je zult alleen maar 0...25 zien. En dat 'mapped' dus supermooi precies op je array bounds. Dus met de modulo operator ga je nooit buiten je array bounds maar ga je als je 't eind bereikt weer netjes naar 't begin (ofwel "wrap around").

Modulo wordt veel gebruikt in encryptie. En, toevallig, ook vaak om bijvoorbeeld random getallen binnen een bepaald bereik te houden; stel je hebt een RNG die altijd gewoon een random byte uitspuugt (0..255) maar je hebt waardes nodig tussen 0..9; dan neem je dus gewoon de output van de RNG en doe je die mod 10. Klaar! Toch? Nou... niet helemaal. Deze methode wordt vaak en veel gebruikt, maar introduceert wel een bias en dat is, coincidentally, waar 't eerder in dit topic over ging. Als je RNG (waarvan ik aanneem dat die zélf unbiased is!) waardes tussen 0 en 249 (dus een mooie ronde 250 mogelijke waardes) zou uitspugen dan was dit een perfect valide methode om getallen tussen 0..9 te genereren; immers: de kans op elk getal is immers 250/10 = 25. Maar omdat je nog 5 extra waardes hebt zullen die dus een bias geven waardoor de cijfers 0..4 dus 1/25^e vaker zullen voorkomen dan de getallen 5..9 (immers 255/10 = 25.5). Dat geeft niet als je die waardes alleen maar gebruikt om te bepalen of je spookje links of rechts moet in Pacman, of de hoogte van het gat te bepalen in Flappy Bird*, maar bouw je er een online pokertoernooi mee of gebruik je 't voor de loterij of, nog erger, in encryptie dan zul je er dus bewust van moeten zijn dat je met de modulo operator een bias introduceert. En dat is precies de reden waarom mijn 'bias-loze' voorbeelden allemaal gewoon waardes boven de 26 weggooien i.p.v. er de modulo operator op los te laten. En dat is ook de reden waarom ik alles bitwise AND met 0x1F; daarmee gooi ik de meest linkse 3 bits ("MSB's") waardoor alle uitkomsten die oorspronkelijk tussen 0..255 liggen zullen vallen tussen 0..31 zonder daar een bias te introduceren en waardoor we dus minder getallen hoeven te discarden die uit de RNG komen. Waarom je 'straffeloos' die 3 bits kunt wegmikken zonder bias te introduceren laat ik even aan jou / de lezer. Ik denk dat ik al (veel) dieper ben gegaan dan nodig

* En geloof me: échte die-hard gamers die een spel tot op 't bot kennen en daar hun leven van gemaakt hebben vinden dit soort dingen feilloos en doen daar óók hun voordeel mee. Punt is dat 't in sommige gevallen helemaal niet zo "erg" is om (een beetje) een bias te hebben.

Note trouwens dat ik nergens heb gezegd dat de Random class geen uniforme distributie geeft; volgens mij is dat wel zo. Ik koos echter voor een CSRNG (in dit geval RNGCryptoServiceProvider) omdat deze minder voorspelbaar is dan Random; dat staat (in principe) los van de distributie. En omdat de RNGCryptoServiceProvider alleen maar bytes geeft moet je dus zelf aan de slag om daar bepaalde ranges (in ons geval 0..25) uit te plukken en ben je dus zélf 'verantwoordelijk' voor 't voorkomen van die bias waar een Random.Next(0, 25) dat (mogelijk) al voor je doet.

Al-met-al dus misschien een beetje overkill, maar on the other hand: je deed 't om er iets van te leren. Now you have

Antwoord:
Bedankt voor je uitleg, ik wist wel wat de modulo oftewel de 'remainder' operator doet, alleen snapte ik het niet in de context waarbij jullie het hadden gebruikt en waarom het nodig was zeg maar om het resterende achteraf in gebruik te nemen.. maar nu snap ik door jouw uitleg waar het naartoe gaat