Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › How to find the most frequent character in a character stream?
New Posts  All Forums:Forum Nav:

How to find the most frequent character in a character stream? - Page 3

post #21 of 41
Quote:
Originally Posted by __Pat__ View Post

Let me clarify then.
Say you have a stream of characters called cs
You have a function that continuously loops, getting the characters from the stream.
In the function you can only use the cs, another single char in memory, which you would put the new cs in, overriding the old one, and one int counter to adjust as they want.

This may be a dumb question, but is cs infinite (at least seemingly) or do you know how many characters are going to come through the stream? I ask this because if cs never ends, how can you ever be sure if any character appears at least 51% of the time? If you know how many characters are going to be in the stream, you could write some pretty ugly and inefficient nested loops to figure out how many different characters there are and their percentage of occurrence.
Gamer
(11 items)
 
   
CPUMotherboardGraphicsGraphics
2500k Asrock z68 extreme 7 gen 3 XFX GTX 260 core 216 XFX GTX 260 core 216 
RAMHard DriveOptical DriveCooling
CORSAIR CMZ8GX3M2A1600C9B  OCZ AGT3-25SAT3-120G R  LITE-ON IHAS224 CORSAIR CAFA70 RT  
OSPowerCase
Windows Vista XON-1100P14HE 1100W  Antec P193 v3 
CPUMotherboardGraphicsRAM
Q9300 EVGA 122-ck-nf68 9600GSO PQI 
Case
Antec P182 
  hide details  
Reply
Gamer
(11 items)
 
   
CPUMotherboardGraphicsGraphics
2500k Asrock z68 extreme 7 gen 3 XFX GTX 260 core 216 XFX GTX 260 core 216 
RAMHard DriveOptical DriveCooling
CORSAIR CMZ8GX3M2A1600C9B  OCZ AGT3-25SAT3-120G R  LITE-ON IHAS224 CORSAIR CAFA70 RT  
OSPowerCase
Windows Vista XON-1100P14HE 1100W  Antec P193 v3 
CPUMotherboardGraphicsRAM
Q9300 EVGA 122-ck-nf68 9600GSO PQI 
Case
Antec P182 
  hide details  
Reply
post #22 of 41
Quote:
Originally Posted by __Pat__ View Post

Ok let's think about it in a different way maybe... The problem is still applicable if it were words not characters. And instead of having a character in memory at a time, we could have a String..

I think someone suggested using a string buffer earlier. If I recall correctly a string buffer is a string...
Gamer
(11 items)
 
   
CPUMotherboardGraphicsGraphics
2500k Asrock z68 extreme 7 gen 3 XFX GTX 260 core 216 XFX GTX 260 core 216 
RAMHard DriveOptical DriveCooling
CORSAIR CMZ8GX3M2A1600C9B  OCZ AGT3-25SAT3-120G R  LITE-ON IHAS224 CORSAIR CAFA70 RT  
OSPowerCase
Windows Vista XON-1100P14HE 1100W  Antec P193 v3 
CPUMotherboardGraphicsRAM
Q9300 EVGA 122-ck-nf68 9600GSO PQI 
Case
Antec P182 
  hide details  
Reply
Gamer
(11 items)
 
   
CPUMotherboardGraphicsGraphics
2500k Asrock z68 extreme 7 gen 3 XFX GTX 260 core 216 XFX GTX 260 core 216 
RAMHard DriveOptical DriveCooling
CORSAIR CMZ8GX3M2A1600C9B  OCZ AGT3-25SAT3-120G R  LITE-ON IHAS224 CORSAIR CAFA70 RT  
OSPowerCase
Windows Vista XON-1100P14HE 1100W  Antec P193 v3 
CPUMotherboardGraphicsRAM
Q9300 EVGA 122-ck-nf68 9600GSO PQI 
Case
Antec P182 
  hide details  
Reply
post #23 of 41
as soon as you can either 1) iterate through the stream more than once (lots of languages will allow you to create a stream iterator and move back and forth) or 2) store an array (of some description) in memory you can solve the problem, without either of those things I see no way of doing it since (even assuming just 26 different characters) there is no way to keep track of the counts of all of them with just a single int (short of having it be a massive huge int which you use as a binary array)


edit: if you changed the counter to being a string instead of an int..its also easily done
First WC, epic
(10 items)
 
  
CPUMotherboardGraphicsGraphics
Intel Core i7 3930K RAMPAGE IV EXTREME NVIDIA GeForce GTX 670 NVIDIA GeForce GTX 670 
RAMRAMRAMRAM
Corsair  Corsair  Corsair  Corsair  
RAMHard Drive
Corsair  Crucial M4 
  hide details  
Reply
First WC, epic
(10 items)
 
  
CPUMotherboardGraphicsGraphics
Intel Core i7 3930K RAMPAGE IV EXTREME NVIDIA GeForce GTX 670 NVIDIA GeForce GTX 670 
RAMRAMRAMRAM
Corsair  Corsair  Corsair  Corsair  
RAMHard Drive
Corsair  Crucial M4 
  hide details  
Reply
post #24 of 41
Are you sure you have the requirements correct? At first glance it doesn't seem possible according to what you've given us to work with.
Big Rig
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i5-2500K ASUS P8Z68-V PRO/GEN3 MSI GTX 670 2GB G.SKILL Ripjaws Z Series 16GB (4x4GB) DDR3 1600 
Hard DriveOptical DriveOSMonitor
Crucial M4 128GB LITE-ON 20X DVD±R DVD Burner with LightScribe Windows 7 Professional (x64) 3 x CrossOver 27Q 27" 2560x1440 
KeyboardPowerCaseMouse
Rosewill RK-9000BR (Cherry MX Brown switches) SEASONIC X750 GOLD 750W COOLER MASTER Sniper Storm Logitech G9 
Audio
ASUS Xonar Essence STX 
  hide details  
Reply
Big Rig
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i5-2500K ASUS P8Z68-V PRO/GEN3 MSI GTX 670 2GB G.SKILL Ripjaws Z Series 16GB (4x4GB) DDR3 1600 
Hard DriveOptical DriveOSMonitor
Crucial M4 128GB LITE-ON 20X DVD±R DVD Burner with LightScribe Windows 7 Professional (x64) 3 x CrossOver 27Q 27" 2560x1440 
KeyboardPowerCaseMouse
Rosewill RK-9000BR (Cherry MX Brown switches) SEASONIC X750 GOLD 750W COOLER MASTER Sniper Storm Logitech G9 
Audio
ASUS Xonar Essence STX 
  hide details  
Reply
post #25 of 41
Quote:
Originally Posted by H Strong View Post

Quote:
Originally Posted by __Pat__ View Post

Ok let's think about it in a different way maybe... The problem is still applicable if it were words not characters. And instead of having a character in memory at a time, we could have a String..

I think someone suggested using a string buffer earlier. If I recall correctly a string buffer is a string...

 

Yeah, I had mentioned using a buffer to store that initial single read then you can use the date how ever you want, but from what I've read in this thread, you are only allowed 'cs' which sounds like a single character, so just a byte, and a integer counter.

CHILZ - Lan Rig
(17 items)
 
CANARY - Main Rig
(16 items)
 
CADILLAC - HTPC
(14 items)
 
CPUMotherboardGraphicsRAM
Intel Xeon X3480 Asus Maximus III Gene AMD 7950 Mushkin Redline 2133 MHz CL9 
Hard DriveHard DriveHard DriveCooling
250 GB Samsung 840 120 GB OCZ Solid 3 60 GB OCZ Vertex 2 Custom Loop 
OSMonitorKeyboardPower
Windows 8 Pro BenQ GL2450 Filco MajesTouch2 Ninja PC P&C Silencer Mk III 600 W 
CaseMouseMouse PadAudio
Spotswood Small Tech Station Tt e-Sports Saphira Monoprice XXL Yamaha R-S300 + JVC Bookshelfs 
Other
Scythe Kama-Panel 3 
CPUMotherboardGraphicsRAM
FX-8150 @ 4.6 GHz Fatal1ty 990FX Pro 9800 GTX+ 512 MB G.Skill Ripjaws X 1866 CL9 
Hard DriveHard DriveCoolingOS
120 GB OCZ Vertex 3 1 TB WD Black 5x 120mm + MCP350 + EK Supreme HF + MicroRes Windows 8 Consumer Preview 
MonitorKeyboardPowerCase
2x Dell U2212HM Logitech G110 Cooler Master 850W Silent Pro Cooler Master 690 II Adv. 
MouseMouse PadAudio
Razer Death Adder 3.5G Staples Gel Cushion Asus Xonar DG + Senn. PC333D 
CPUMotherboardGraphicsRAM
Q6600 Acer X1800 ATI 5670 2 GB Kingston 
Hard DriveOptical DriveOSMonitor
2 TB WD Green Asus BD-R Windows 7 Home Premium Sony 50" LCD 
KeyboardPowerCaseMouse
Acer Media 220 W SFF Acer X1800 Acer Optical 
Mouse PadAudio
The TV cabinet Denon 2808 7.1 AVR + Dahlquist 350W 8" Sub + Kl... 
  hide details  
Reply
CHILZ - Lan Rig
(17 items)
 
CANARY - Main Rig
(16 items)
 
CADILLAC - HTPC
(14 items)
 
CPUMotherboardGraphicsRAM
Intel Xeon X3480 Asus Maximus III Gene AMD 7950 Mushkin Redline 2133 MHz CL9 
Hard DriveHard DriveHard DriveCooling
250 GB Samsung 840 120 GB OCZ Solid 3 60 GB OCZ Vertex 2 Custom Loop 
OSMonitorKeyboardPower
Windows 8 Pro BenQ GL2450 Filco MajesTouch2 Ninja PC P&C Silencer Mk III 600 W 
CaseMouseMouse PadAudio
Spotswood Small Tech Station Tt e-Sports Saphira Monoprice XXL Yamaha R-S300 + JVC Bookshelfs 
Other
Scythe Kama-Panel 3 
CPUMotherboardGraphicsRAM
FX-8150 @ 4.6 GHz Fatal1ty 990FX Pro 9800 GTX+ 512 MB G.Skill Ripjaws X 1866 CL9 
Hard DriveHard DriveCoolingOS
120 GB OCZ Vertex 3 1 TB WD Black 5x 120mm + MCP350 + EK Supreme HF + MicroRes Windows 8 Consumer Preview 
MonitorKeyboardPowerCase
2x Dell U2212HM Logitech G110 Cooler Master 850W Silent Pro Cooler Master 690 II Adv. 
MouseMouse PadAudio
Razer Death Adder 3.5G Staples Gel Cushion Asus Xonar DG + Senn. PC333D 
CPUMotherboardGraphicsRAM
Q6600 Acer X1800 ATI 5670 2 GB Kingston 
Hard DriveOptical DriveOSMonitor
2 TB WD Green Asus BD-R Windows 7 Home Premium Sony 50" LCD 
KeyboardPowerCaseMouse
Acer Media 220 W SFF Acer X1800 Acer Optical 
Mouse PadAudio
The TV cabinet Denon 2808 7.1 AVR + Dahlquist 350W 8" Sub + Kl... 
  hide details  
Reply
post #26 of 41
Thread Starter 
I found the solution in my googling guys... So simple yet powerful!

http://stackoverflow.com/questions/3740371/finding-the-max-repeated-element-in-an-array

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html
Quote:
When we move the pointer forward over an element e:

If the counter is 0, we set the current candidate to e and we set the counter to 1.
If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
*facepalm*
Edited by __Pat__ - 7/18/12 at 11:56am
Seiryuu
(13 items)
 
  
CPUMotherboardGraphicsRAM
i5-750 @ 3.00GHz Intel DP55WB Sapphire HD 5850 @ 950/1200 1.212V Kingston 2x2GB DDR3 1333.3 
Hard DriveOSMonitorPower
1TB WD Black, 1TB WD Green Win 7 Ultimate 64 bit Samsung P2370H Thermaltake ToughPower 750W 
Case
Thermaltake M9 Black 
  hide details  
Reply
Seiryuu
(13 items)
 
  
CPUMotherboardGraphicsRAM
i5-750 @ 3.00GHz Intel DP55WB Sapphire HD 5850 @ 950/1200 1.212V Kingston 2x2GB DDR3 1333.3 
Hard DriveOSMonitorPower
1TB WD Black, 1TB WD Green Win 7 Ultimate 64 bit Samsung P2370H Thermaltake ToughPower 750W 
Case
Thermaltake M9 Black 
  hide details  
Reply
post #27 of 41
Quote:
Originally Posted by __Pat__ View Post

Ok I got this question asked to me and I've been trying to find the answer all day to no avail!
If there is a character stream, with one character having an occurrence rate of 51% or more, how can we find the most frequent character if only a single character, and a counter can be stored in the memory at a time.
We can only access each character a single time, since this is a stream.

Based on the bold section above, that solution doesn't fit your requirements.


Edit: I think it also assumes the characters are already sorted eg: A, A, A, B,B,B,B,C,C,C,C
Edited by CrashZero - 7/18/12 at 12:28pm
First WC, epic
(10 items)
 
  
CPUMotherboardGraphicsGraphics
Intel Core i7 3930K RAMPAGE IV EXTREME NVIDIA GeForce GTX 670 NVIDIA GeForce GTX 670 
RAMRAMRAMRAM
Corsair  Corsair  Corsair  Corsair  
RAMHard Drive
Corsair  Crucial M4 
  hide details  
Reply
First WC, epic
(10 items)
 
  
CPUMotherboardGraphicsGraphics
Intel Core i7 3930K RAMPAGE IV EXTREME NVIDIA GeForce GTX 670 NVIDIA GeForce GTX 670 
RAMRAMRAMRAM
Corsair  Corsair  Corsair  Corsair  
RAMHard Drive
Corsair  Crucial M4 
  hide details  
Reply
post #28 of 41
Quote:
Originally Posted by CrashZero View Post

Based on the bold section above, that solution doesn't fit your requirements.

Sure it does. You only need the counter and one character in memory, and the current character in the stream.
Big Rig
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i5-2500K ASUS P8Z68-V PRO/GEN3 MSI GTX 670 2GB G.SKILL Ripjaws Z Series 16GB (4x4GB) DDR3 1600 
Hard DriveOptical DriveOSMonitor
Crucial M4 128GB LITE-ON 20X DVD±R DVD Burner with LightScribe Windows 7 Professional (x64) 3 x CrossOver 27Q 27" 2560x1440 
KeyboardPowerCaseMouse
Rosewill RK-9000BR (Cherry MX Brown switches) SEASONIC X750 GOLD 750W COOLER MASTER Sniper Storm Logitech G9 
Audio
ASUS Xonar Essence STX 
  hide details  
Reply
Big Rig
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i5-2500K ASUS P8Z68-V PRO/GEN3 MSI GTX 670 2GB G.SKILL Ripjaws Z Series 16GB (4x4GB) DDR3 1600 
Hard DriveOptical DriveOSMonitor
Crucial M4 128GB LITE-ON 20X DVD±R DVD Burner with LightScribe Windows 7 Professional (x64) 3 x CrossOver 27Q 27" 2560x1440 
KeyboardPowerCaseMouse
Rosewill RK-9000BR (Cherry MX Brown switches) SEASONIC X750 GOLD 750W COOLER MASTER Sniper Storm Logitech G9 
Audio
ASUS Xonar Essence STX 
  hide details  
Reply
post #29 of 41
Quote:
Originally Posted by __Pat__ View Post

I found the solution in my googling guys... So simple yet powerful!
http://stackoverflow.com/questions/3740371/finding-the-max-repeated-element-in-an-array
http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html
Quote:
When we move the pointer forward over an element e:
If the counter is 0, we set the current candidate to e and we set the counter to 1.
If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
*facepalm*

Hey, glad you found the solution. smile.gif

But I am a bit confused. The algorithm you linked me to doesn't quite seem to work for the following sequence of characters:

AABBAACCCAB

The result using that algorithm comes out to be B (with integer = 1) whereas it's clear that the most frequently occurring character is A.

Am I missing some part or condition of the algorithm? Have I not applied the algorithm correctly?
Could some one check this over for me.
 
Desktop
(13 items)
 
MacBook Pro 13"
(6 items)
 
CPUGraphicsRAMHard Drive
Intel i5 480m@2.67GHz AMD Radeon Mobility 5650 4GB DDR3 500GB 
OSMonitor
Windows 7 64bit HP 15.6" 1366x768 
CPUMotherboardGraphicsRAM
E7500 Intel...:( MSI GTS250 1GB 2GB 
Hard DriveOSMonitorPower
250GB Windows XP 17" LG CRT 1280x768@85hz 400W 
CPUGraphicsRAMHard Drive
Intel i5 @ 2.5 GHz Intel HD4000 4 GB DDR3 @ 1600 MHz 500 GB @ 5400 RPM 
OSMonitor
OSX Lion 13.3" @ 1280 x 800 
  hide details  
Reply
 
Desktop
(13 items)
 
MacBook Pro 13"
(6 items)
 
CPUGraphicsRAMHard Drive
Intel i5 480m@2.67GHz AMD Radeon Mobility 5650 4GB DDR3 500GB 
OSMonitor
Windows 7 64bit HP 15.6" 1366x768 
CPUMotherboardGraphicsRAM
E7500 Intel...:( MSI GTS250 1GB 2GB 
Hard DriveOSMonitorPower
250GB Windows XP 17" LG CRT 1280x768@85hz 400W 
CPUGraphicsRAMHard Drive
Intel i5 @ 2.5 GHz Intel HD4000 4 GB DDR3 @ 1600 MHz 500 GB @ 5400 RPM 
OSMonitor
OSX Lion 13.3" @ 1280 x 800 
  hide details  
Reply
post #30 of 41
Quote:
Originally Posted by {Unregistered} View Post

*facepalm*
Hey, glad you found the solution. smile.gif
But I am a bit confused. The algorithm you linked me to doesn't quite seem to work for the following sequence of characters:
AABBAACCCAB
The result using that algorithm comes out to be B (with integer = 1) whereas it's clear that the most frequently occurring character is A.
Am I missing some part or condition of the algorithm? Have I not applied the algorithm correctly?
Could some one check this over for me.

the way that algorithm is formed you got the correct answer. This is what happening:

as you work down the stream you get A = 2 then you hit the B's which decrements the counter by 2 leaving you at 0 which then changes the char in the array to A again and counter goes to 2. Then you hit the C's which decrements the counter for the first 2 C's then change the letter to C and counter to 1. after that you hit B which decrements it to zero then you hit B which changes the letter and increments counter. This algorithm isn't a solution the the problem being asked.
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › How to find the most frequent character in a character stream?