Unique Characters Only

[Mike Sanders]

run as...

awk -f uniqueChars.awk

output...

Input string: Mary had a little lamb who's fleece was white as snow...
Unique chars: Mary hdlitembwo'sfcn.

script...

BEGIN {

a = "Mary had a little lamb who's fleece was white as snow..."
b = uniqueChars(a)

print "Input string: " a
print "Unique chars: " b

}

function uniqueChars(str, x, y, c, tmp, uniqueStr) {

y = length(str)
uniqueStr = ""
delete tmp # clear array for each new string

while(++x <= y) {
c = substr(str, x, 1)
if (!(c in tmp)) {
uniqueStr = uniqueStr c
tmp[c]
}
}

return uniqueStr

}

[Janis Papanagnou]

If you want to avoid the substr() function calls in the loop and don't
mind using non-standard (GNU Awk) features you can also use split():

function uniqueChars (t, s, n, i, c, o, seen)
{
delete seen
n = split (t, s, "")
for (i=1; i<=n; i++)
if (!seen[c = s[i]]++)
o = o c

return o
}

{
printf "In:\t%s\nOut:\t%s\n", $0, uniqueChars($0)
}


(Just for a variant.)

Janis

Post by Mike Sanders
run as...
awk -f uniqueChars.awk
output...
Input string: Mary had a little lamb who's fleece was white as snow...
Unique chars: Mary hdlitembwo'sfcn.
script...
BEGIN {
a = "Mary had a little lamb who's fleece was white as snow..."
b = uniqueChars(a)
print "Input string: " a
print "Unique chars: " b
}
function uniqueChars(str, x, y, c, tmp, uniqueStr) {
y = length(str)
uniqueStr = ""
delete tmp # clear array for each new string
while(++x <= y) {
c = substr(str, x, 1)
if (!(c in tmp)) {
uniqueStr = uniqueStr c
tmp[c]
}
}
return uniqueStr
}

[Mike Sanders]

Post by Janis Papanagnou
If you want to avoid the substr() function calls in the loop and don't
function uniqueChars (t, s, n, i, c, o, seen)
{
delete seen
n = split (t, s, "")
for (i=1; i<=n; i++)
if (!seen[c = s[i]]++)
o = o c
return o
}
{
printf "In:\t%s\nOut:\t%s\n", $0, uniqueChars($0)
}
(Just for a variant.)
Janis

Janis you are good! =)

[J Naman]

Post by Janis Papanagnou
If you want to avoid the substr() function calls in the loop and don't
function uniqueChars (t, s, n, i, c, o, seen)
{
delete seen
n = split (t, s, "")
for (i=1; i<=n; i++)
if (!seen[c = s[i]]++)
o = o c
return o
}
{
printf "In:\t%s\nOut:\t%s\n", $0, uniqueChars($0)
}
(Just for a variant.)
Janis

Post by Mike Sanders
run as...
awk -f uniqueChars.awk
output...
Input string: Mary had a little lamb who's fleece was white as snow...
Unique chars: Mary hdlitembwo'sfcn.
script...
BEGIN {
a = "Mary had a little lamb who's fleece was white as snow..."
b = uniqueChars(a)
print "Input string: " a
print "Unique chars: " b
}
function uniqueChars(str, x, y, c, tmp, uniqueStr) {
y = length(str)
uniqueStr = ""
delete tmp # clear array for each new string
while(++x <= y) {
c = substr(str, x, 1)
if (!(c in tmp)) {
uniqueStr = uniqueStr c
tmp[c]
}
}
return uniqueStr
}

The Unique Chars Only discussion of string Op variants -- substr() split() index() -- reminded me of an interesting note in the most excellent Awk book, 2nd Edition. They benchmark split() vs substr() for single character operations and substr() is 40% faster than split(). I always assumed that split() was faster.

[Janis Papanagnou]

Post by J Naman
The Unique Chars Only discussion of string Op variants -- substr()
split() index() -- reminded me of an interesting note in the most
excellent Awk book, 2nd Edition. They benchmark split() vs substr()
for single character operations and substr() is 40% faster than
split(). I always assumed that split() was faster.

In many cases it's not obvious until it is measured in practice!
Specifically you (usually) have to consider also the data sizes.

(Also note that the Book may not consider GNU Awk's special case
of split'ing characters that may perform better or worse.)

And you may also consider other factors (if the speed difference
is not that significant, as with the small data set we have here),
e.g. what construct is better maintainable (with various aspects).
I'd expect that substr(s,p,1) is extremely fast because that should
basically be only an indexed access on a linear array[*], and such
operations are often performed in one CPU cycle. Considering other
implementations for this substring from other languages, say, s[p]
will not give the impression of a performance problem - there's no
explicit function call but there shouldn't be much difference given
the primitivity of this operation[**].

The reason for my split()-based variant was to have no function call
overheads and algorithmically removing an "invariant" from the loop
(preparing the data). Note that the access of the split-array might
also be a [fast] indexed access, or it may be a [fast] hash-array
access (as I think it is in Awk).

But that all said you also have to consider that arrays are memory
consumptive! If you have huge data sets it will be considerable
worse to use split with arrays than simply index-access a string.
(It doesn't matter here, but be aware.)

In short; I don't think that efficiency is here an issue. That all
considered I'd *not* use the split method - which is, as mentioned,
not even standard with FS="" - to be on the safe side.

Janis

[*] A caveat e.g. in case of variable-width characters in arrays
used for string representation; it might be more expensive than it
appears at first glance.

[**] Performance issues usually arise on higher algorithmic levels.

[yeti]

You can use `ìndex` to avoid adding the same char multiple times to the
result string. That may or may not be faster than using an additional
array, I've not benchmarked it (yet?). You may call me Vroomfondel
today.

[Vroomfondel]

Reading beyond this line equals signing an implicit "Non Laughing
Agrement". ;-)


Only minimally tested:

function uniqueChars(str,_c,_i,_seen) {
_seen=""
for(_i=1;_i<=length(str);_i++) {
if(0<index(str,_c=substr(str,_i,1)))
if(index(_seen,_c)<1)
_seen=_seen _c
}
return _seen
}

Maybe the assumption that array ops are more expensive than string ops
is wrong and this idea is worse than the original.


Next stop: Recursion!
(Just joking!)

[Mike Sanders]

Post by Vroomfondel
Reading beyond this line equals signing an implicit "Non Laughing
Agrement". ;-)
function uniqueChars(str,_c,_i,_seen) {
_seen=""
for(_i=1;_i<=length(str);_i++) {
if(0<index(str,_c=substr(str,_i,1)))
if(index(_seen,_c)<1)
_seen=_seen _c
}
return _seen
}
Maybe the assumption that array ops are more expensive than string ops
is wrong and this idea is worse than the original.

But then again, maybe not. I must study this more (thank you!).

Post by Vroomfondel
Next stop: Recursion!
(Just joking!)

Chuckle, GNU acronyms come to mind...

[Mike Sanders]

You can use `??ndex` to avoid adding the same char multiple times to the
result string. That may or may not be faster than using an additional
array, I've not benchmarked it (yet?). You may call me Vroomfondel
today.

Hey, sounds interesting, please post your complete code.

[Mike Sanders]

Post by Mike Sanders
function uniqueChars(str, x, y, c, tmp, uniqueStr) {
y = length(str)
uniqueStr = ""
delete tmp # clear array for each new string
while(++x <= y) {
c = substr(str, x, 1)
if (!(c in tmp)) {
uniqueStr = uniqueStr c
tmp[c]
}
}
return uniqueStr
}

okay, got rid of tmp array...

function uniqueChars(str, x, y, c, uniqueStr) {

y = length(str)
uniqueStr = ""

while(++x <= y) {
c = substr(str, x, 1)
if (index(uniqueStr, c) == 0) uniqueStr = uniqueStr c
}

return uniqueStr

}

[Ed Morton]

Post by Mike Sanders
run as...
awk -f uniqueChars.awk
output...
Input string: Mary had a little lamb who's fleece was white as snow...
Unique chars: Mary hdlitembwo'sfcn.
script...
BEGIN {
a = "Mary had a little lamb who's fleece was white as snow..."
b = uniqueChars(a)
print "Input string: " a
print "Unique chars: " b
}
function uniqueChars(str, x, y, c, tmp, uniqueStr) {
y = length(str)
uniqueStr = ""
delete tmp # clear array for each new string

You don't need to do that `delete` - just having "tmp" listed in the
args list will re-init it every time the function is called. Removing
that statement will also make your script portable to awks than don't
support `delete array` (but most, possibly all, modern awks do support
that even though it's technically still undefined behavior).

Post by Mike Sanders
while(++x <= y) {

Using a `while` instead of `for` loop for that makes your code a bit
less clear, a bit more fragile (what if `x` gets set above?), and a bit
harder to maintain (what if in future you need to increment x by 2 every
iteration?). It's not worth saving the few characters over the
traditional `for ( x=1; x<=y; x++ )`

Post by Mike Sanders
c = substr(str, x, 1)
if (!(c in tmp)) {

Idiomatically that'd be implemented as

if ( !tmp[c]++ ) {

and then you'd remove the `tmp[c]` below but the array in that case is
almost always named `seen[]` rather than `tmp[]`.

Post by Mike Sanders
uniqueStr = uniqueStr c
tmp[c]
}
}
return uniqueStr
}

Alternatively, if the order of the characters returned doesn't matter,
you could do:

function uniqueChars(str, x, y, c, tmp, uniqueStr) {

y = length(str)
uniqueStr = ""
for ( x=1; x<=y; x++ ) {
tmp[substr(str,x,1)]
}
for ( c in tmp ) {
uniqueStr = uniqueStr c
}

return uniqueStr

}

I don't expect that to be any faster or anything, it's just different,
but if you have GNU awk then it can be tweaked to:

function uniqueChars(str, x, y, c, tmp, uniqueStr) {

y = length(str)
uniqueStr = ""
for ( x=1; x<=y; x++ ) {
tmp[substr(str,x,1)]
}
PROCINFO["sorted_in"] = "@ind_str_asc"
for ( c in tmp ) {
uniqueStr = uniqueStr c
}

return uniqueStr

}

and then it'll return the unique characters sorted in alphabetic order
which may be useful.

Regards,

Ed.

[Mike Sanders]

Post by Ed Morton
You don't need to do that `delete` - just having "tmp" listed in the
args list will re-init it every time the function is called. Removing
that statement will also make your script portable to awks than don't
support `delete array` (but most, possibly all, modern awks do support
that even though it's technically still undefined behavior).

You know I wondered about that, thought I'd play it safe, but yeah,
noted: array always created anew, good to know.

Post by Ed Morton

Post by Mike Sanders
while(++x <= y) {

Using a `while` instead of `for` loop for that makes your code a bit
less clear, a bit more fragile (what if `x` gets set above?), and a bit
harder to maintain (what if in future you need to increment x by 2 every
iteration?).

Aye.

Post by Ed Morton
It's not worth saving the few characters over the
traditional `for ( x=1; x<=y; x++ )`

Post by Mike Sanders
c = substr(str, x, 1)
if (!(c in tmp)) {

Idiomatically that'd be implemented as
if ( !tmp[c]++ ) {
and then you'd remove the `tmp[c]` below but the array in that case is
almost always named `seen[]` rather than `tmp[]`.

Post by Mike Sanders
uniqueStr = uniqueStr c
tmp[c]
}
}
return uniqueStr
}

Alternatively, if the order of the characters returned doesn't matter,
function uniqueChars(str, x, y, c, tmp, uniqueStr) {
y = length(str)
uniqueStr = ""
for ( x=1; x<=y; x++ ) {
tmp[substr(str,x,1)]
}
for ( c in tmp ) {
uniqueStr = uniqueStr c
}
return uniqueStr
}
I don't expect that to be any faster or anything, it's just different,
function uniqueChars(str, x, y, c, tmp, uniqueStr) {
y = length(str)
uniqueStr = ""
for ( x=1; x<=y; x++ ) {
tmp[substr(str,x,1)]
}
for ( c in tmp ) {
uniqueStr = uniqueStr c
}
return uniqueStr
}
and then it'll return the unique characters sorted in alphabetic order
which may be useful.

Must add these examples to my notes.