Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Reelya]

You should see if it's faster and simpler if you use dummy nodes for head/tail. That way you can write the whole thing without any if statements for edge cases, since there are no edge cases then.

EDIT: Also be careful of if statements which assume index==0 or that the node is head as the "true" case. that's because of branch prediction. The compiler assumes your default if-statement branch is the most likely case (since it cannot predict how the program will actually function).

In Add for example, the first thing you check is "if (Head == null)", so your compiler is optimizing the code for the default case of "empty list". This means you're missing out on a little speed on non-empty lists. The fix is as simple as flipping the if and else branches and checking if (head != null). It's the same in your insert function, where the "true" branch is the one that calls the exception. Try making that the else branch instead.

[TheBiggerFish]

What do you mean, dummy nodes?  This is supposed to be an actual linked list, there are going to be times when it's supposed to have nothing in it.

[Reelya]

Making blank nodes for the head and tail reduces the amount of edge cases, the amount of code generated, and speeds up the linked list operations in general. The cost is a couple of empty nodes doing nothing, but that's offset by the code itself being smaller.

[Reelya]

Anyway here's a rough outline of a version with dummy nodes for head and tail, it's got a few C++ style elements in it, and i haven't run this through a compiler however, so there are probably a bunch of typos and you should treat this as pseudocode:

Spoiler (click to show/hide)

Code: [Select]

template <typename T> class node
{
public:
T data, *prev, *next;

node(T &_data): data(_data), prev(0), next(0) {}

friend template <typename T> class list;
}

template <typename T> class list
{
node<T> *head, *tail;
unsigned int count;

list() : count(0)
{
head = new node<T>;
tail = new node<T>;
head->next = tail;
tail->prev = head;
}

void insertAfter(node<T> *oldnode, T data) // this function should be private
{
node<T> *newnode = new node<T>(data);
newnode->prev = oldnode;
newnode->next = oldnode->next;
oldnode->next->prev = newnode;
oldnode->next = newnode;
count++;
}

T removeNode(node<T> node)
{
if(node != null)
{
T data = node->data;
// remove node
node->prev->next = node->next;
node->next->prev = node->prev;
delete node;
count--;
return data;
}
}

void push(T& data)
{
insertAfter(head, data);
}

void pushback(T& data)
{
insertAfter(tail->prev, data);
}

T pop()
{
if(head->next != tail)
{
return(remove(head->next));
}
}

T popback()
{
if(tail->prev != head)
{
return(remove(tail->prev));
}
}

node<T> getNodeAt(unsigned int location)
{
if(location * 2 < count) // in the lower half (avoid the division)
{
node<T> *node = head;
for(int i = 0; i < location; ++i)
{
node = node->next;
}
return node;
}
else if(location < count) // in the upper half
{
node<T> *node = tail->prev;
for(int i = count - 1; i > location; ++i)
{
node = node->prev;
}
return node;
}

return null;
}

void insert(unsigned int location, T &newdata)
{
node<T> node = getNodeAt(location);
if(node != null)
{
insertAfter(node, newdata);
}
}

void remove(unsigned int location)
{
node<T> node = getNodeAt(location);
// if(node != null) // removed this check as removeNode also checks
{
removeNode(node);
}
}
}


[TheBiggerFish]

....Yeah, that's not even C#.

[Reelya]

It's C#'s smarter brother.

[TheBiggerFish]

And what language is that?

[da_nang]

C++ from the looks of it.

[Gatleos]

Spoiler (click to show/hide)

Thought some people here might appreciate this. I just finished putting way too much effort into a university project that scrapes Wikipedia using their search API to create a visual navigation tool.

It's a node app, so run this in the root directory once you have that installed:

Code: [Select]

npm install
npm start


[Parsely]

I could use some assistance with a C# project.
Overview of the project: I'm working on a multithreading practice thing in Visual Studio 2015. It has two methods: one called Producers that creates unique messages and pushes them to a queue, and another called Consumers that writes a queued message to the console and removes it from the queue. The methods also sleep briefly to simulate lengthy processes. The messages are created using a class called Message that overrides ToString() so that calling the object returns a string containing the message's unique ID, the current time, and a unique string.

The Problem: When I run it, it always makes and consumes exactly the provided amount of messages, but in the printed messages the strings are not unique. Sometimes it clones two or more of the same message. The only reason for this happening that I can think of is that my lock statement is not working the way I think it should, and two tasks are making a message before one can increment msgProduced. I've been doing reading on the lock statement but I can't seem to figure out why it isn't locking the resource like it should. IF that is indeed the problem.

Code: (This will compile if you dump it in Visual Studio or what have you.) [Select]

using System;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;

namespace MultiThreading
{
    class TaskProgram
    {
        // number of messages to print
        private const int MessageCount = 1000;

        // number of threads should be half the number of processors
        private static int threadCount = Environment.ProcessorCount / 2;

        // keep track of the number of messages produced and consumed
        private static int msgProduced = 0;
        private static int msgConsumed = 0;

        // queue (FIFO) to hold messages
        static Queue<Message> queue = new Queue<Message>();
        // object to lock on
        private static readonly object MySharedResourceLock = new object();

        static void Main(string[] args)
        {
            // task array to hold threads
            Task[] producers = new Task[threadCount];

            // runs all the tasks in the array
            for (int i = 0; i < producers.Length; i++)
            {
                producers[i] = Task.Run(() => Producers(MessageCount));
            }

            Task[] consumers = new Task[threadCount];

            for (int i = 0; i < consumers.Length; i++)
            {
                consumers[i] = Task.Run(() => Consumers(MessageCount));
            }

            // wait for all the tasks in the task arrays to finish before proceeding
            Task.WaitAll(producers);
            Task.WaitAll(consumers);

            // write the total messages produced/consumed (should be MessageCount), and the final count of the queue (should be 0) to the console
            Console.WriteLine("Total messages produced: " + msgProduced + " | Total messages consumed: " + msgConsumed + " | Final Queue Count: " + queue.Count);

            // keep the program from exiting so we can see the results
            Console.ReadKey();
        }

        // produce messages and push them to the queue, takes the number of messages to be produced as a parameter
        static void Producers(int tasksForProducer)
        {
            // object that contains a random time in milliseconds
            Random rand = new Random(DateTime.Now.Millisecond);

            // loop to produce the requested amount of messages
            for (int i = 0; i < tasksForProducer; ++i)
            {
                /* changes to the queue are destructive, so these actions should be behind a lock
                the lock statement tries to acquire the shared resource object
                if another lock has already acquired the object, it waits until */
                lock (MySharedResourceLock)
                {
                    // create a new message, feed it msgProduced to use as a unique ID
                    Message message = new Message(msgProduced);
                    // add the message to the queue
                    queue.Enqueue(message);
                    // increment msgProduced
                    msgProduced++;
                }
                // wait for 23-97ms
                Thread.Sleep(rand.Next(23, 97));
                // exit the loop when the number of messages is equal to the number of messages to write
                if (msgProduced == tasksForProducer)
                    return;
            }
        }

        // Consumers method loops once for each task
        static void Consumers(int tasksForConsumer)
        {
            Random rand = new Random(DateTime.Now.Millisecond);

            for (int i = 0; i < tasksForConsumer; ++i)
            {
                lock (MySharedResourceLock)
                {
                    try
                    {
                        Message msg = null;
                        // make msg equal to the Message object in the queue, then dequeue it (the Message object)
                        msg = queue.Dequeue();
                        // if msg isn't null, write it to the console
                        if (null != msg)
                            Console.WriteLine(msg);
                        // increment msgConsumed
                        msgConsumed++;
                    }
                    catch
                    {

                    }
                }
                Thread.Sleep(rand.Next(17, 37));
                if (msgConsumed == tasksForConsumer)
                    return;
            }
        }

        // Class that produces unique messages
        public class Message
        {
            // Instance variables
            private static int count = 0;
            private static DateTime currentTime;
            private static string arbitraryText;

            // Message constructor
            public Message(int taskID)
            {
                count = taskID;
                currentTime = DateTime.Now;
                arbitraryText = $"{taskID} bottles of beer on the wall.";
            }

            // Index is a unique increasing integer
            public int Index
            {
                // Shorthand/auto accessors
                get
                {
                    return count;
                }
                set
                {
                    count = value;
                }

            }

            // Timestamp is the current time and date when the message is created
            public DateTime Timestamp
            {
                get
                {
                    return currentTime;
                }
                set
                {
                    currentTime = value;
                }

            }

            // Text is a unique string
            public string Text
            {
                get
                {
                    return arbitraryText;
                }
                set
                {
                    arbitraryText = value;
                }

            }

            // Overrides default Object() method ToString() to make it do what I want it to
            public override string ToString()
            {
                return Index.ToString("0000") + "|" + Timestamp + "|" + Text;
            }
        }
    }
}
I would highly appreciate any advice.

Edit: I tried using a mutex instead of the lock statement and I had the same problem.

[nogoodnames]

I would highly appreciate any advice.

The lock is working properly, the problem is caused by the Message field variables being static. Each time a new message is created, all the static variables in other Message instances are updated to have the new values as well.

Also, the check to see if the number of tasks completed equals the number of assigned tasks should occur at the start of each lock block. The way you're doing it now can allow the counts to increment before the check is performed, causing it to fail and making the task go through the full For loop before completing.

[Reelya]

Are you sure about that nogoodnames?

The fields that are statics are the ones that track how many messages have been sent. They're meant to be static, because that's how the threads are communicating what the next available ID number is.

The part which creates the message is not static:

                    Message message = new Message(msgProduced); // <= not actually static
                    // add the message to the queue
                    queue.Enqueue(message);
                    // increment msgProduced
                    msgProduced++; // <- this is static on purpose, so that all threads get the updated value

[nogoodnames]

I'm talking about the field variables of the actual Message class. These ones:

Code: [Select]

// Class that produces unique messages
        public class Message
        {
            // Instance variables
            private static int count = 0;
            private static DateTime currentTime;
            private static string arbitraryText;

And yes, I'm sure they're the problem. I tested it myself.

[Reelya]

Ah yeah I missed the "Message" body. i assumed Message was some sort of primitive to the language. I really hate the way C# and Java programs are laid out, really hard to read past all the boilerplate. Does every function and variable really need to explicitly list 17 different parameters before the name?

[Parsely]

I would highly appreciate any advice.

The lock is working properly, the problem is caused by the Message field variables being static. Each time a new message is created, all the static variables in other Message instances are updated to have the new values as well.

Also, the check to see if the number of tasks completed equals the number of assigned tasks should occur at the start of each lock block. The way you're doing it now can allow the counts to increment before the check is performed, causing it to fail and making the task go through the full For loop before completing.

Holy crap, thank you so much! That was a really elusive problem (for me). Thanks for the other tip as well, I implemented it.

Ah yeah I missed the "Message" body. i assumed Message was some sort of primitive to the language. I really hate the way C# and Java programs are laid out, really hard to read past all the boilerplate. Does every function and variable really need to explicitly list 17 different parameters before the name?

In this case not paying attention to my types screwed me, but as with any language, the more I practice and reread the documentation the more natural it becomes. Explicit typing is definitely a big sticking point for beginners, but once overcome it has its advantages. JS can have some pretty sneaky typing bugs if you're not careful, and if you don't do any error handling it won't tell you anything is wrong until you've tied your code into knots.