Asp Forum - Unique Key Generation - microsoft.public.vb.general.discussion

BeeJ

10/15/2011 2:48:00 AM

I need to generate a unique Key for a data array to allow indexing into
a different object. e.g. a row would have a key and the key might be
used as the Key to a Collection storing data related to that row and a
column.
The array is of String() only in the form of Col().Row()
As in
Private Type tListRow
asRow() As String
End Type
Private atCol() As tListRow

atCol(lKeyCol).asRow(lRow) = sKey

Since this is a large array I need to keep the Key smallish.
The array can be sorted and rows deleted so the Key cannot be simply
the Index since there would then be duplicates of the Key (when rows
deleted and then added).

I cannot simply add columns since the data that might be added using
the Key could be related to one or more columns in each row. But the
expect qty is small so using a Key into a collection will work.

So far all I can come up with is to use
sKey = Cdbl(Now)
But that generates a longish string.
Using Now should be OK since the array does not exist too very long and
I doubt (ha ha) that the Clock will be reset to create duplicates of
this.

Anyway, is there a better way to do this?

22 Answers

BeeJ

10/15/2011 4:22:00 AM

Also, the data may not be unique so a hash to generate a key would not
work. Unless I just do not understand that concept.
Also, the Key generation should be fairly fast.

ralph

10/15/2011 6:19:00 AM

On Fri, 14 Oct 2011 19:48:14 -0700, BeeJ <nospam@spamnot.com> wrote:

>I need to generate a unique Key for a data array to allow indexing into
>a different object. e.g. a row would have a key and the key might be
>used as the Key to a Collection storing data related to that row and a
>column.
>The array is of String() only in the form of Col().Row()
>As in
> Private Type tListRow
> asRow() As String
> End Type
> Private atCol() As tListRow
>
> atCol(lKeyCol).asRow(lRow) = sKey
>
>Since this is a large array I need to keep the Key smallish.
>The array can be sorted and rows deleted so the Key cannot be simply
>the Index since there would then be duplicates of the Key (when rows
>deleted and then added).
>
>I cannot simply add columns since the data that might be added using
>the Key could be related to one or more columns in each row. But the
>expect qty is small so using a Key into a collection will work.
>
>So far all I can come up with is to use
> sKey = Cdbl(Now)
>But that generates a longish string.
>Using Now should be OK since the array does not exist too very long and
>I doubt (ha ha) that the Clock will be reset to create duplicates of
>this.
>
>Anyway, is there a better way to do this?
>

Probably not since you say the need is of relativily short duration.

I usually create a simple Function with a static which I increment
when called. Something like this ...

Public Function FetchKey() As String
Static lKey As Long
lKey = lKey + 1
FetchKey = "A" & CStr(lKey) ' creates an alphanumeric key
End Function

If you need something larger than a positive long then add a check for
the max and then increment the leading alpha portion and start over.

I also often use a Fetch function that produces only Alphabetical
characters. It uses two statics, one to hold the last key provided,
and one to hold the next letter, rolling over at 26, and thus produces
keys like this ...
"A"
"B"
...
"AA"
"BA"
....

Using an alphanumeric key is useful if, as you mentioned, you plan on
using it with a Collection since the Item method is overloaded to
handle both Indexes and Keys. Due to ETC (Evil Type Coercion) VB can
on occasion confuse a numeric key for an index with unsatisfactory
results.

The Static only works for the lifetime of the program. If you need it
to advance over several lifetimes then you'll need to preserve it some
where (INI, simple text, Registry, etc.)

Using a function like either of the above will generate a 'smaller'
key but take more clicks. So likely won't meet your requirements on
speed. However, when working with arrays for a dynamic store it is
usually the basic manipulations (inserting and deleting) that take the
most time - concentrating on them is likely to provide better
performance than worrying about the length of a Key.

The length of a key must have some impact*, but like all such
'performance' issues you will just have to test within your problem
domain.

[*VB Collections convert all keys to its internal hashtable so later
retrieval is quick, but they still have to be 'hashed' in the first
place. And of course of any string comparisons will be affected by
length.]

-ralph
[I see you are still in love with UDTs. <g>]

DanS

10/15/2011 12:53:00 PM

BeeJ <nospam@spamnot.com> wrote in
news:j7as9g$i1o$1@speranza.aioe.org:

> The array is of String() only in the form of Col().Row()
> As in
> Private Type tListRow
> asRow() As String
> End Type
> Private atCol() As tListRow
>
> atCol(lKeyCol).asRow(lRow) = sKey
>

Is this the real code ?

I'm just wondering why a Type would be used when there only one member in it.

Thorsten Albers

10/15/2011 1:17:00 PM

BeeJ <nospam@spamnot.com> schrieb im Beitrag
<j7as9g$i1o$1@speranza.aioe.org>...
> I need to generate a unique Key for a data array to allow indexing into
> a different object. e.g. a row would have a key and the key might be
> used as the Key to a Collection storing data related to that row and a
> column.
>
> Since this is a large array I need to keep the Key smallish.
> The array can be sorted and rows deleted so the Key cannot be simply
> the Index since there would then be duplicates of the Key (when rows
> deleted and then added).

Function GetUniqueKey() As String
Const LONG_MAX As Long = &H7FFFFFFF
Const LONG_MIN As Long = &H80000000
Const ULONG_MIN As Long = &HFFFFFFFF

Static UKey As Long

Dim lCount As Long

If UKey = ULONG_MAX Then
Exit Function ' No more key available
ElseIf UKey = LONG_MAX Then
UKey = LONG_MIN
Else
UKey = UKey + 1
End If

If UKey <= &H000000FF Then
lCount = 6
ElseIf UKey <= &H0000FFFF Then
lCount = 4
ElseIf UKey <= &H00FFFFFF Then
lCount = 2
End If

GetUniqueKey = String$(lCount, "0") & Hex$(UKey)

End Function

Key range: 1 - 4.294.967.295
Key size: 8 characters (= 16 Bytes)

By packing each BYTE of the DWORD = 4 BYTE key in one character (1 Unicode
character = 2 BYTES) you can reduce the key size to 4 characters = 8 Bytes:

Private Type DWORD
Value As Long
End Type

Private Type DWORD_BYTES
LoByteLoWord As Byte
HiByteLoWord As Byte
LoByteHiWord As Byte
HiByteHiWord As Byte
End Type

Dim DW As DWORD, DWB As DWORD_BYTES

DW.Value = UKey
DWB = DW
GetUniqueKey = ChrW$(DWB.HiByteHiWord) _
ChrW$(DWB.LoByteHiWord) _
ChrW$(DWB.HiByteLoWord) _
ChrW$(DWB.LoByteLOWord)

By packing each WORD of the DWORD = 2 WORD key in one character (1 Unicode
character = 1 WORD) you can reduce the key size to 2 characters = 4 Bytes:

Private Type DWORD
Value As Long
End Type

Private Type DWORD_WORDS
LoWord As Integer
HiWord As Integer
End Type

Dim DW As DWORD, DWW As DWORD_WORDS

DW.Value = UKey
DWW = DW
GetUniqueKey = ChrW$(DWW.HiWord) & ChrW$(DWW.LoWord)

I didn't check but in the last sample ChrW$() maybe fails with certain
values (e.g. FFFFh).

--
Thorsten Albers

gudea at gmx.de

BeeJ

10/17/2011 1:53:00 AM

Thanks.

Decided to take a little from each.
Using a Hex$ of the count right now starting at 1 (all non-zero
entries).
This compresses the digits somewhat.

So how about a F.a.s.t Radix Alphabet Function to compress even more?

so something like the following...
please review and comment. mistakes? make it faster please?
Thanks!
I guess all the printable characters is the limit.
This one goes 0..9A..Z for now.
Fun!
'
' mdlRadix
'
Option Explicit

' ===========================================
Public Const cRadixBin As Integer = 2
Public Const cRadixOct As Integer = 8
Public Const cRadixDec As Integer = 10
Public Const cRadixHex As Integer = 16
Public Const cRadixAbet As Integer = 36
' ===========================================

Private m_avPow() As Variant

Public Function RadixToDec(sNum As String, xRad As Integer) As Variant

Dim lIx As Long
Dim dRes As Variant
Dim sVal As String
Dim dVal As Variant
Dim lLength As Long

dRes = CDec(dRes)
dVal = CDec(dVal)

lLength = Len(sNum)
sNum = UCase$(sNum)

For lIx = 1 To lLength
sVal = Asc(Mid$(sNum, lLength - lIx + 1, 1))
Select Case sVal
Case vbKey0 To vbKey9
dVal = sVal - vbKey0

Case vbKeyA To vbKeyZ
dVal = sVal - 55

Case Else
' error
End Select
dRes = dRes + pow(xRad, (lIx - 1)) * dVal
Next lIx

RadixToDec = dRes

End Function 'RadixToDec

Private Function pow(ByVal lBase As Long, ByVal lExp As Long) As
Variant

' calculate powers of numbers.

Dim lIdx As Long

pow = CDec(lBase)
If lExp = 0 Then
pow = 1
Else
For lIdx = 1 To lExp - 1
pow = pow * lBase
Next
End If

End Function 'Pow

Public Function DecToRadix(ByVal vDec As Variant, ByVal iRadix As
Integer, Optional bSuffix As Boolean = False, Optional bDecCommas As
Boolean = False) As String

On Error GoTo DecToRadixErr

Dim dLen As Double
Dim sResult As String
Dim sDigit As String
Dim vVal As Variant
Dim vNorm As Variant
Dim iX As Integer

vVal = CDec(0)
vNorm = CDec(0)

If vDec = 0 Then
DecToRadix = "0"
Else
dLen = (Log(vDec) / Log(iRadix)) + 1
If dLen <> Int(dLen) Then dLen = Int(dLen) + 1

For iX = 0 To dLen - 1
vNorm = (iRadix ^ (dLen - iX - 1))
vVal = Fix(Val(vDec) / (vNorm))

Select Case vVal
Case 10 To 35
sDigit = Chr$(65 + Val(vVal) - 10)

Case Else
sDigit = Int(Val(vDec) / iRadix ^ (dLen - iX - 1))

End Select
sResult = sResult & sDigit
vVal = (iRadix) ^ (dLen - iX - 1)
vDec = vDec - (Int(Val(vDec) / vVal) * vVal)
Next iX
Do
If Left$(sResult, 1) = "0" Then
sResult = Mid$(sResult, 2)
Else
Exit Do
End If
Loop
If (iRadix = cRadixDec) And bDecCommas Then
DecToRadix = FormatNbr(Val(sResult))
Else
DecToRadix = sResult
End If
End If
If bSuffix Then
Select Case iRadix
Case cRadixBin
DecToRadix = DecToRadix & " (B)"
Case cRadixOct
DecToRadix = DecToRadix & " (O)"
Case cRadixDec
DecToRadix = DecToRadix & " (D)"
Case cRadixHex
DecToRadix = DecToRadix & " (H)"
Case cRadixAbet
DecToRadix = DecToRadix & " (A)"
Case Else
DecToRadix = DecToRadix & " (" & CStr(iRadix) & ")"
End Select
End If

DecToRadixExit:
Exit Function

DecToRadixErr:
'Resume
DecToRadix = "#ERROR#"
Resume DecToRadixExit

End Function 'DecToRadix

Jim Mack

10/17/2011 11:11:00 AM

> Thanks.
>
> Decided to take a little from each.
> Using a Hex$ of the count right now starting at 1 (all non-zero entries).
> This compresses the digits somewhat.
>
> So how about a F.a.s.t Radix Alphabet Function to compress even more?
>
> so something like the following...
> please review and comment. mistakes? make it faster please?
> Thanks!
> I guess all the printable characters is the limit.
> This one goes 0..9A..Z for now.
> Fun!

This is going to fail one of your initial criteria -- it's going to be
slow. It's too general-purpose and needlessly complex for the
conditions you specified.

You said that the number of keys would be fairly small, so you could
restrict this to a single base (say 94) with a limit of MAXLONG or
less. The technique is simply repeated division by 94 and add 33 to
each result, and deal with the remainder. The value then contains only
printable characters (33..126) and is 9x compacted.

You could cut the amount of code by 2/3, stick to integer math and
avoid string concats. Also, if the idea is just to generate keys, you
don't need the reverse operation at all, right?

Really, for a small key range where speed is an issue, CStr(key) would
be fast and reasonably compact.

--
Jim

> '
> ' mdlRadix
> '
> Option Explicit
>
> ' ===========================================
> Public Const cRadixBin As Integer = 2
> Public Const cRadixOct As Integer = 8
> Public Const cRadixDec As Integer = 10
> Public Const cRadixHex As Integer = 16
> Public Const cRadixAbet As Integer = 36
> ' ===========================================
>
> Private m_avPow() As Variant
>
> Public Function RadixToDec(sNum As String, xRad As Integer) As Variant
>
> Dim lIx As Long
> Dim dRes As Variant
> Dim sVal As String
> Dim dVal As Variant
> Dim lLength As Long
>
> dRes = CDec(dRes)
> dVal = CDec(dVal)
>
> lLength = Len(sNum)
> sNum = UCase$(sNum)
>
> For lIx = 1 To lLength
> sVal = Asc(Mid$(sNum, lLength - lIx + 1, 1))
> Select Case sVal
> Case vbKey0 To vbKey9
> dVal = sVal - vbKey0
>
> Case vbKeyA To vbKeyZ
> dVal = sVal - 55
>
> Case Else
> ' error
> End Select
> dRes = dRes + pow(xRad, (lIx - 1)) * dVal
> Next lIx
>
> RadixToDec = dRes
>
> End Function 'RadixToDec
>
> Private Function pow(ByVal lBase As Long, ByVal lExp As Long) As Variant
>
> ' calculate powers of numbers.
>
> Dim lIdx As Long
>
> pow = CDec(lBase)
> If lExp = 0 Then
> pow = 1
> Else
> For lIdx = 1 To lExp - 1
> pow = pow * lBase
> Next
> End If
>
> End Function 'Pow
>
> Public Function DecToRadix(ByVal vDec As Variant, ByVal iRadix As
> Integer, Optional bSuffix As Boolean = False, Optional bDecCommas As
> Boolean = False) As String
>
> On Error GoTo DecToRadixErr
>
> Dim dLen As Double
> Dim sResult As String
> Dim sDigit As String
> Dim vVal As Variant
> Dim vNorm As Variant
> Dim iX As Integer
>
> vVal = CDec(0)
> vNorm = CDec(0)
>
> If vDec = 0 Then
> DecToRadix = "0"
> Else
> dLen = (Log(vDec) / Log(iRadix)) + 1
> If dLen <> Int(dLen) Then dLen = Int(dLen) + 1
>
> For iX = 0 To dLen - 1
> vNorm = (iRadix ^ (dLen - iX - 1))
> vVal = Fix(Val(vDec) / (vNorm))
>
> Select Case vVal
> Case 10 To 35
> sDigit = Chr$(65 + Val(vVal) - 10)
>
> Case Else
> sDigit = Int(Val(vDec) / iRadix ^ (dLen - iX - 1))
>
> End Select
> sResult = sResult & sDigit
> vVal = (iRadix) ^ (dLen - iX - 1)
> vDec = vDec - (Int(Val(vDec) / vVal) * vVal)
> Next iX
> Do
> If Left$(sResult, 1) = "0" Then
> sResult = Mid$(sResult, 2)
> Else
> Exit Do
> End If
> Loop
> If (iRadix = cRadixDec) And bDecCommas Then
> DecToRadix = FormatNbr(Val(sResult))
> Else
> DecToRadix = sResult
> End If
> End If
> If bSuffix Then
> Select Case iRadix
> Case cRadixBin
> DecToRadix = DecToRadix & " (B)"
> Case cRadixOct
> DecToRadix = DecToRadix & " (O)"
> Case cRadixDec
> DecToRadix = DecToRadix & " (D)"
> Case cRadixHex
> DecToRadix = DecToRadix & " (H)"
> Case cRadixAbet
> DecToRadix = DecToRadix & " (A)"
> Case Else
> DecToRadix = DecToRadix & " (" & CStr(iRadix) & ")"
> End Select
> End If
>
> DecToRadixExit:
> Exit Function
>
> DecToRadixErr:
> 'Resume
> DecToRadix = "#ERROR#"
> Resume DecToRadixExit
>
> End Function 'DecToRadix

--
Jim

BeeJ

10/18/2011 2:48:00 AM

Size trumps speed.
And according to my speed tests, the use of higher radix numbers does
not substantially affect the overall operations.

Even though the list may be over 100,000+++ items, the speed relates to
usually only one or two dozen per user initiated update.
But 100,000 * 10 vs 100,000 * 5 is slightly more significant.

And did you mean Long math rather than Integer math?

So how would I avoid string concat in the methods I proposed?

Thanks for you interest.

Jim Mack

10/18/2011 3:17:00 AM

> Size trumps speed.
> And according to my speed tests, the use of higher radix numbers does not
> substantially affect the overall operations.

I'm not sure what point you're addressing. You can get both size and
speed by writing the code to work with a single large base, like 94. A
4-character key string handles up to 78 million keys (94^4 values).
Three characters is enough for 830,000 keys (94^3).

> Even though the list may be over 100,000+++ items, the speed relates to
> usually only one or two dozen per user initiated update.
> But 100,000 * 10 vs 100,000 * 5 is slightly more significant.
>
> And did you mean Long math rather than Integer math?

I meant integer as opposed to float, variant, decimal etc.
>
> So how would I avoid string concat in the methods I proposed?

I didn't look at what you proposed in depth because it's immediately
obvious that it's way overcoded -- a general purpose solution to a
specific issue. But if you're using base 94 it doesn't matter -- three
or four characters is nothing.

Here's a function that will generate base94 keys. It's fixed at 4
characters (78 million keys) but it's simple to modify for less.

Private Function NumTo94(ByVal InVal As Long) As String

' Returns a 4-character string, the base94 coding
' of the incoming value, or a null string if the
' value is too large to fit into 4 characters.

Const MAX_VALUE As Long = 78074896 ' 94 ^ 4

Static Place(1 To 3) As Long
Static bHere As Boolean

Dim Idx As Long
Dim Char As Long
Dim Result As String

If Not bHere Then
bHere = True
For Idx = 1 To 3
Place(4 - Idx) = 94& ^ Idx
Next
End If

If InVal < MAX_VALUE Then
Result = "!!!!" ' = string$(4, 33)
For Idx = 1 To 3
Char = InVal \ Place(Idx)
If Char <> 0 Then
InVal = InVal - (Char * Place(Idx))
Mid$(Result, Idx) = ChrW$(Char + 33)
End If
Next
Mid$(Result, 4) = ChrW$(InVal + 33)
End If

NumTo94 = Result

End Function ' NumTo94

' For a little more speed you could unroll the loop and lose
' the array. If you can't see how to do that, just ask.

' Also, to verify results here's the inverse:

Private Function NumFrom94(Value94 As String) As Long

Static Place(1 To 4) As Long
Static bHere As Boolean

Dim Idx As Long
Dim Char As Long
Dim Result As Long

If Not bHere Then
bHere = True
For Idx = 1 To 3
Place(4 - Idx) = 94& ^ Idx
Next
Place(4) = 1
End If

For Idx = 1 To 4
Char = AscW(Mid$(Value94, Idx, 1)) - 33
Result = Result + (Char * Place(Idx))
Next

NumFrom94 = Result

End Function ' NumFrom94

--
Jim

BeeJ

10/18/2011 6:15:00 AM

Your subs are much faster but use more memory than mime.
If we could loose the leading !s then yours would be much more memory
efficient.

Thorsten Albers

10/18/2011 11:32:00 AM

BeeJ <nospam@spamnot.com> schrieb im Beitrag
<j7ipcs$m97$1@speranza.aioe.org>...
> Size trumps speed.
> And according to my speed tests, the use of higher radix numbers does
> not substantially affect the overall operations.
>
> Even though the list may be over 100,000+++ items, the speed relates to
> usually only one or two dozen per user initiated update.
> But 100,000 * 10 vs 100,000 * 5 is slightly more significant.
>
>
> And did you mean Long math rather than Integer math?
>
> So how would I avoid string concat in the methods I proposed?

What I can't understand is why you do not simply change
Private Type tListRow
asRow() As String
End Type
to
Private Type tListRow
alRow() As Long
End Type

This is the least amount of memory used for the key possible.

Why is it necessary for you to have the key as string?

--
Thorsten Albers

gudea at gmx.de

microsoft.public.vb.general.discussion

Unique Key Generation

BeeJ

BeeJ

ralph

DanS

Thorsten Albers

BeeJ

Jim Mack

BeeJ

Jim Mack

BeeJ

Thorsten Albers

x Login to ForumsZone