|
Here is the question..
There are 10,000 entries in text file which has following format
"name:telephone number:address"
We need to make a program that will read that file and look up the name, telephone number or address from any one of them in O(log n) complexity. So obviously, I'm gonna store each entry in array and sort them and do binary search to look up a particular variable, as it needed to O(logn) in complexity.
Now, my question is should I copy the array to another three arrays, each of them sorted according to three parameters(telephone numbers, names, address) and then perform look up search. Is there any better way of doing it without taking so much space because basically to make program in O(logn) complexity, you are taking 3 times the space as compared to original linear search.
Suggest the best way of doing it. Any help will be appreciated.
Shivam
|
|
|
|
|
as name, number, and address are strings, they wouldn't need to get stored multiple times; all you need to duplicate is pointers/references to them. And with say 250 chars per telephone, you would need less than 10 MB of memory anyway.
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
Thank you for the response but this not what I'm trying to ask. So far, I've made a class called telephone with three member variables of String type, those are names, address and telephone number. Then I made array of telephone class of size 10,000. Now this array has randomly distributed telephone entries but I need arrange sorted order according to each three variable, i.e. telephone, name and address so that I could perform binary search.
Let say user enter telephone number then my program will perform binary search on list sorted according to telephone numbers.
If user enter name then my program will perform search on the list which is started according to name and similarly it will do same procedure for address. So basically you need three list, but can you think of any other method of doing this?
Thank you
Shivam
|
|
|
|
|
what I said is this, using your terminology: you make 10,000 Telephone instances, and store each of them in three different arrays, then sort each of these arrays. That is still only 10,0000 Telephones, not 30,000.
as for sorting stuff, there are smarter ways to represent data. Either come up with something yourself, or make use of existing ones, see e.g. the .NET collections.
Finally, as this is homework, you're supposed to do the work yourself.
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
Oh, I got it. Thank you very much.
Shivam
|
|
|
|
|
You're welcome.
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
How about three of Dictionary<string,Telephone> ?
Or a spell check tree?
Or this thing[^], whatever it is.
|
|
|
|
|
Ok, its a homework of data structure course, so u can't expect us to use pre-written classes of .NET. We have to write complete program on our own . But the suggestions you gave are really good, I'll definitely look into them.
Thank you
Shivam
|
|
|
|
|
I have problem with this code is draw ships many time
if u have any idea about it
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Linq;
using System.Diagnostics;
using System.Text;
using System.Windows.Forms;
namespace DrawingGeomerticShips
{
public partial class Form1 : System.Windows.Forms.Form
{
private Pen nPen;
public Form1():base()
{
InitializeComponent();
nPen = new Pen(Color.Black);
}
protected override void Dispose(bool disposing)
{
if (disposing)
{
if (components != null)
{
components.Dispose();
}
}
base.Dispose(disposing);
}
//private Bitmap ColorMap;
public enum dModes : int
{
Line,
Rectangle,
Ellipse,
Brush,
Path,
Text,
Eraser
}
//private Bitmap bmp;
private Bitmap bmp2;
private Graphics g2;
private Color clr= Color.Red;
//private Color clr2 = Color.blue;
private int StartX;
private int StartY;
private int EndX;
private int EndY;
private int BoxWidth;
private int BoxHeight;
private System.Drawing.Drawing2D.GraphicsPath mpath = new System.Drawing.Drawing2D.GraphicsPath();
private dModes dmode;
private int xLoc;
private int yLoc;
//private dStyles dstyle = dStyles.Outline;
private Int16 pWidth = 1;
//private Cursor c = new Cursor(GetEmbeddedFile("Whiteboard.ColorPicker.ico"));
//private Cursor er = new Cursor(GetEmbeddedFile("Whiteboard.Eraser.ico"));
private bool isDraw;
private PointF pF;
private PointF pFOld;
[System.Runtime.InteropServices.DllImport("user32.dll", EntryPoint="HideCaret", ExactSpelling=true, CharSet=System.Runtime.InteropServices.CharSet.Ansi, SetLastError=true)]
public static extern Int32 HideCaret(Int32 hwnd);
private bool allow;
[System.Runtime.InteropServices.DllImport("user32.dll", EntryPoint="ShowCaret", ExactSpelling=true, CharSet=System.Runtime.InteropServices.CharSet.Ansi, SetLastError=true)]
public static extern Int32 ShowCaret(Int32 hwnd);
[System.Runtime.InteropServices.DllImport("user32.dll", EntryPoint="CreateCaret", ExactSpelling=true, CharSet=System.Runtime.InteropServices.CharSet.Ansi, SetLastError=true)]
public static extern Int32 CreateCaret(Int32 hwnd, Int32 hBitmap, Int32 nWidth, Int32 nHeight);
[System.Runtime.InteropServices.DllImport("user32.dll", EntryPoint="SetCaretPos", ExactSpelling=true, CharSet=System.Runtime.InteropServices.CharSet.Ansi, SetLastError=true)]
public static extern Int32 SetCaretPos(Int32 x, Int32 y);
string txt = null;
public Color color
{
get
{
return clr;
}
}
public Int16 penWidth
{
get
{
return pWidth;
}
set
{
pWidth = value;
nPen.Width = pWidth;
}
}
public void DrawPath(MouseEventArgs e) //path
{
}
public void DrawBrush(MouseEventArgs e) //brush
{
}
public void DrawLine(MouseEventArgs e) //line
{
}
private void SetLineW(Int16 MyW)
{
if (MyW < 1)
{
MyW = 1;
}
penWidth = MyW;
}
public void DrawRectangle(System.Windows.Forms.MouseEventArgs e) //rectangle
{
xLoc = 0;
yLoc = 0;
if (e.X > StartX)
{
BoxWidth = e.X - StartX;
xLoc = StartX;
}
else
{
BoxWidth = StartX - e.X;
xLoc = e.X;
}
if (e.Y > StartY)
{
BoxHeight = e.Y - StartY;
yLoc = StartY;
}
else
{
BoxHeight = StartY - e.Y;
yLoc = e.Y;
}
// DrawArea.CreateGraphics().DrawRectangle(nPen, xLoc, yLoc, BoxWidth, BoxHeight);
// DrawArea.Refresh();
}
public void DrawEllipse(System.Windows.Forms.MouseEventArgs e) //ellipse
{
xLoc = 0;
yLoc = 0;
if (e.X > StartX)
{
BoxWidth = e.X - StartX;
xLoc = StartX;
}
else
{
BoxWidth = StartX - e.X;
xLoc = e.X;
}
if (e.Y > StartY)
{
BoxHeight = e.Y - StartY;
yLoc = StartY;
}
else
{
BoxHeight = StartY - e.Y;
yLoc = e.Y;
}
// DrawArea.CreateGraphics().DrawEllipse(nPen, xLoc, yLoc, BoxWidth, BoxHeight);
//DrawArea.Refresh();
}
public void Eraser(System.Windows.Forms.MouseEventArgs e) //eraser
{
DrawArea.Refresh();
DrawArea.CreateGraphics().FillRectangle(Brushes.White, e.X - 1, e.Y, penWidth, penWidth);
DrawArea.CreateGraphics().DrawRectangle(Pens.Black, e.X - 1, e.Y, penWidth, penWidth);
}
private void Form1_Load(object sender, EventArgs e)
{
//color = Color.Black;
bmp2 = new Bitmap(DrawArea.Width, DrawArea.Height);
g2 = Graphics.FromImage(bmp2);
g2.SmoothingMode = SmoothingMode.AntiAlias;
}
private void DrawArea_MouseDown(object sender, System.Windows.Forms.MouseEventArgs e)
{
if (e.Button == MouseButtons.Left)
{
isDraw = true;
StartX = e.X;
StartY = e.Y;
if (dmode == dModes.Text) //if text mode is selected it creates a caret on the clicked position
{
pF = new PointF((float)(e.X), (float)(e.Y - FontHeight / 2.0));
if (pF.Equals(pFOld))
{
}
else
{
allow = true;
}
DrawArea.Focus();
CreateCaret(DrawArea.Handle.ToInt32(), 0, 2, this.FontHeight);
//SetCaretPos(pF.X, pF.Y);
ShowCaret(DrawArea.Handle.ToInt32());
}
}
}
private void DrawArea_MouseMove(object sender, MouseEventArgs e)
{
if (isDraw)
{
switch (dmode)
{
case dModes.Ellipse:
DrawArea.CreateGraphics().DrawEllipse(nPen, xLoc, yLoc, BoxWidth, BoxHeight);
break;
case dModes.Line:
EndX = e.X;
EndY = e.Y;
// DrawArea.Refresh();
DrawArea.CreateGraphics().DrawLine(nPen, StartX, StartY, EndX, EndY);
break;
case dModes.Brush:
mpath.AddLine(e.X, e.Y, e.X, e.Y);
DrawArea.CreateGraphics().DrawPath(nPen, mpath);
break;
case dModes.Rectangle:
DrawArea.CreateGraphics().DrawRectangle(nPen, xLoc, yLoc, BoxWidth, BoxHeight);
break;
case dModes.Path:
EndX = e.X;
EndY = e.Y;
//DrawArea.Refresh();
DrawArea.CreateGraphics().DrawLine(nPen, StartX, StartY, EndX, EndY);
break;
case dModes.Eraser:
Eraser(e);
g2.FillRectangle(Brushes.White, e.X, e.Y, pWidth, pWidth);
break;
}
}
}
private void DrawArea_MouseUp(object sender, MouseEventArgs e)
{
isDraw = false;
switch (dmode)
{
case dModes.Ellipse:
g2.FillEllipse(new SolidBrush(clr), xLoc, yLoc, BoxWidth, BoxHeight);
break;
case dModes.Line:
g2.DrawLine(nPen, StartX, StartY, EndX, EndY);
break;
case dModes.Brush:
g2.DrawPath(nPen, mpath);
mpath.Reset();
break;
case dModes.Rectangle:
g2.DrawRectangle(nPen, xLoc, yLoc, BoxWidth, BoxHeight);
break;
case dModes.Path:
mpath.AddLine(StartX, StartY, e.X, e.Y);
g2.DrawPath(nPen, mpath);
// mpath.Reset();
break;
case dModes.Text:
if (allow)
{
g2.DrawString(txt, this.Font, new SolidBrush(clr), pFOld);
}
allow = false;
txt = "";
//tbox.Clear()
break;
}
DrawArea.BackgroundImage = bmp2;
}
private void DrawArea_KeyPress(object sender, System.Windows.Forms.KeyPressEventArgs e)
{
}
private void button1_Click(object sender, EventArgs e)
{
dmode = dModes.Ellipse;
mpath.Reset();
hide_Caret();
}
private void button2_Click(object sender, EventArgs e)
{
dmode = dModes.Rectangle;
mpath.Reset();
hide_Caret();
}
private void button7_Click(object sender, EventArgs e)
{
dmode = dModes.Line;
mpath.Reset();
hide_Caret();
}
private void button4_Click(object sender, EventArgs e)
{
dmode = dModes.Brush;
mpath.Reset();
hide_Caret();
}
private void button5_Click(object sender, EventArgs e)
{
dmode = dModes.Path;
hide_Caret();
}
private void button6_Click(object sender, EventArgs e)
{
dmode = dModes.Eraser;
hide_Caret();
}
public object hide_Caret() //hides the caret
{
if (txt != "")
{
g2.DrawString(txt, this.Font, new SolidBrush(clr), pFOld);
}
DrawArea.BackgroundImage= bmp2;
allow = false;
HideCaret(DrawArea.Handle.ToInt32());
txt = "";
//INSTANT C# NOTE: Inserted the following 'return' since all code paths must return a value in C#:
return null;
}
private void DiColor_Paint(object sender, PaintEventArgs e)
{
}
private void DiColor_MouseClick(object sender, MouseEventArgs e)
{
ColorDialog MyDC = new ColorDialog();
DialogResult Dr = MyDC.ShowDialog();
if (Dr == DialogResult.OK && MyDC.Color != null)
{
this.clr = MyDC.Color;
DiColor.BackColor = clr;
}
}
private void trackBar1_Scroll(object sender, EventArgs e)
{
SetLineW(Convert.ToInt16(trackBar1.Value));
}
private void button3_Click(object sender, EventArgs e)
{
dmode = dModes.Text;
mpath.Reset();
}
private void Form1_KeyPress(object sender, KeyPressEventArgs e)
{
txt += e.KeyChar;
this.Refresh();
//INSTANT C# TODO TASK: The 'On Error Resume Next' statement is not converted by Instant C#:
if (e.KeyChar == '\b') //backspace
{
txt = txt.Substring(0, txt.Length - 2);
e.Handled = true;
}
g2.PageUnit = GraphicsUnit.Pixel;
//SetCaretPos(pF.X + g2.MeasureString(txt, new Font("arial", 8)).Width, pF.Y);
DrawArea.CreateGraphics().DrawString(txt, this.Font, new SolidBrush(clr), pF.X, pF.Y);
pFOld = pF;
}
private void DrawArea_Paint(object sender, PaintEventArgs e)
{
}
}
}
|
|
|
|
|
This is totally unreadable; put your code between <pre></pre> tags, and mark the lines that have the problem.
I must get a clever new signature for 2011.
|
|
|
|
|
That is unformatted and unreadable. I think I saw some CreateGraphics which is probably very wrong. Please edit your question to include PRE tags, then read this[^].
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
My list collection has several items.
I would like to add/update this collection list with the value I have while looping through the collection using foreach...
How can I check if the value already exists (update it) and if it does not exist, then add it?
Do I have to have another collection or array to hold the unique values while looping through the collection list?
Thanks
|
|
|
|
|
You can use a HashSet<T> to hold unique values, but adding elements to any collection while looping through it is not a good practice. Tell us a little more about what you want to do, and maybe we can give you a better approach.
|
|
|
|
|
Basically my existing list is as follows:
Basically my existing list is as follows:
private List<monitor> results = new List<monitor>(); //hold the messages...
There are fields in monitor class i.e. Field1, Field2, Field3, ...
private void UpdateList(string strField1Value)
{
//loop through results collection
//chek if Field1 in results is as same as strField1value
//if strNewvalue is already present in results collection, then only update that row with the new fields
//else add the new row to the results collection...
}
|
|
|
|
|
Ok, then use a Dictionary<TKey, TValue> instead of a List or HashSet. Use the field1 as the key of that dictionary, and the monitor objects as values. This way you will not need to check anything:
Dictionary<string, monitor> results = new Dictionary<string, monitor>();
void UpdateList(monitor mon)
{
results[mon.Field1] = mon;
}
As it is that simple, you can even delete the UpdateList method and just modify the Dicionary as required. No loop needed for this.
|
|
|
|
|
Dictionary<string, monitor> results = new Dictionary<string, monitor>();
It says, Tkey, Tvalue is required
|
|
|
|
|
Yes, sorry, I made a little mistake. I've fixted it, read the post again.
|
|
|
|
|
Yes it needed a little fix.
I'd appreciate you don't do stealth fixes though, as they may make a thread incomprehensible.
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
Yes, you're right. I am quite an absentminded person . I will try to quote my fixes in the future. Thanks for the advise.
|
|
|
|
|
A warning: if the key value (strField1Value) of some object changes after it has been added to the dictionary, then the dictionary is no longer valid, i.e. it needs updating (removing and re-inserting the object).
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
|
|
|
|
|
I might do it this way:
public class MyCollection : List<MyItem>
{
public bool AddUnique(MyItem newItem)
{
bool found = false;
if (!this.Contains(newItem))
{
foreach (MyItem item in this)
{
if (item.MyProperty == newItem.MyProperty)
{
found = true;
break;
}
}
}
else
{
found = true;
}
if (!found)
{
this.Add(newItem);
}
return found;
}
}
".45 ACP - because shooting twice is just silly" - JSOP, 2010 ----- You can never have too much ammo - unless you're swimming, or on fire. - JSOP, 2010 ----- "Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass." - Dale Earnhardt, 1997
|
|
|
|
|
I think I asked the same question like a week ago or so and you offered me this solution so basically him and I requeired the same thing. if you didnt responce to him I would have responded. good call tho.
|
|
|
|
|
Sorry John, but this isn't a great solution if the size of the data gets too large. Basically, every time you add a record you increase the amount of time it takes to search for a new item just to see if it can be added. I recently had to rework some code that somebody had put together like this to find and add files into a list of monitored files. As you can imagine, it works fine when there are only a few items in the list, but the algorithm completely falls apart when you start getting to the few tens of thousands.
A simpler way is to use a Dictionary. As in:
private Dictionary<string, MyItem> _items = new Dictionary<string, MyItem>();
public void Add(MyItem value)
{
if (!_items.ContainsKey(value.MyProperty))
{
_items.Add(value.MyProperty, value);
}
} Alternatively if the OP is using .NET 3.5+, a HashSet provides a good choice because it removes the duplication where the dictionary contains MyProperty both in the value, and in the key.
|
|
|
|
|
I merely provided a solution. He didn't specify how big the collection would get, but until said collection gets to an unwieldy size, my answer is fine, especisally given his apparent lack of programming ability is concerned. Besides that, "duplicate" can mean any number of things, and my solution covers the possibilites.
He could use a HashSet with some extension methods, but honestly, that's beyond his level of skill. I was merely considering the audience, that's all.
".45 ACP - because shooting twice is just silly" - JSOP, 2010 ----- You can never have too much ammo - unless you're swimming, or on fire. - JSOP, 2010 ----- "Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass." - Dale Earnhardt, 1997
|
|
|
|
|
hi m doing work with AT commands with c# could not find any AT command for voice msg. there are AT commands for SMS and voice call also but i could not find any command for voice msg. is it possible to snd or receive voice msg through AT commands???
|
|
|
|
|