Print

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

[Shadowlord]

Pretty sure tree from carbon it's open source.

Pretty sure the cron daemon is open source.

[Skyrunner]

Oh well.

Suppose we have a computing system including N independent processors, threads, devices, executors etc (set P = {p_1,...,p_N}). There are also M tasks (set T = {t_1,...,t_M}) being passed in the said computing system to be handled. We know how much time (or any other meaningful resource in a particular case) is needed to process a given t_i from T, some tau(t_i), by either processor, that is each task can be executed by each of the processors in the same amount of time, and note that processors can't delegate some of the tasks assigned to them to any other processor. The objective is to find such schedule that the total amount of time to execute all tasks on either processor would be minimal.

A schedule is a mapping A_R : T -> P such that if A_R(t_i) = p_j, task t_i from T is said to be assigned to processor p_j from P. A schedule can be also defined as a partition of set T into N disjunctive subsets.

The criterium (that is objective function) to determine how good the outcoming schedule (and thus the algorithm we've used) is is the following: f_r = max f_j (1<=j<=n) -> min, where f_j = tau(t_j_1) + ... + tau(t_j_k) stands for how much time it requires for processor p_j to execute all the tasks (k' tasks alltogether) assigned to it.

This definitely doesn't sound related the cron/crontab utility on linux, which just executes things at a given time. As for the actual algorithm, my instinct (which is fairly rusty for algorithmic problems) tells me that this is sorta a knapsack problem.

[Reelya]

The knapsack problem is a bit different: fill knapsack(s) of volume V as full as possible from N items, but leftovers don't matter. The bin-packing problem is a little closer: take N items and pack them into the least amount of bins of volume V.

But scheduling is about filling a set amount of bins as empty as possible, using all N items:

https://en.wikipedia.org/wiki/Scheduling_(computing)
https://en.wikipedia.org/wiki/Job_shop_scheduling
https://en.wikipedia.org/wiki/Job_shop_scheduling#Offline_makespan_minimization
https://en.wikipedia.org/wiki/Multiprocessor_scheduling
https://en.wikipedia.org/wiki/Partition_problem

My guess is that the lecturer was talking about one of the algorithms addressed here, but referring to it as the "cron algorithm".

[Willfor]

: D N-Body simulator for something I'm working on.

This took far longer than I wanted it to. Also, the display sizes are not accurate representations of the data at work.

[Bumber]

I'm trying to finish my raytracer for a class assignment. I'm almost done, but my helper functions are causing errors:

Code: [Select]

1>c:\users\bumber\documents\visual studio 2013\projects\proj2\proj2\raytrace.hh(425): error C2662: 'void raytrace::Scene::compute_ray(int,int,const std::shared_ptr<const raytrace::Image>,std::shared_ptr<raytrace::Vector4>,std::shared_ptr<raytrace::Vector4>)' : cannot convert 'this' pointer from 'const raytrace::Scene' to 'raytrace::Scene &'
1>          Conversion loses qualifiers
1>c:\users\bumber\documents\visual studio 2013\projects\proj2\proj2\raytrace.hh(426): error C2662: 'bool raytrace::Scene::trace_ray(std::shared_ptr<raytrace::Vector4>,std::shared_ptr<raytrace::Vector4>,std::shared_ptr<raytrace::SceneObject>)' : cannot convert 'this' pointer from 'const raytrace::Scene' to 'raytrace::Scene &'
1>          Conversion loses qualifiers
1>c:\users\bumber\documents\visual studio 2013\projects\proj2\proj2\raytrace.hh(429): error C2662: 'std::shared_ptr<gmath::Vector<double,3>> raytrace::Scene::lambert_shade(const std::shared_ptr<const raytrace::Intersection>,const std::shared_ptr<const raytrace::SceneObject>)' : cannot convert 'this' pointer from 'const raytrace::Scene' to 'raytrace::Scene &'
1>          Conversion loses qualifiersI'm not even sure where the type of the class is coming into play.

Source:
http://pastebin.com/mqzYizbp
http://pastebin.com/dFRUJCBP
http://pastebin.com/A8h5KT79

[Reelya]

You can't take a reference to a const variable, because a reference means changeable.

You can fix this a few ways: remove the const tag where it's being added, cast the const variable to the non-const type, or change the function so that it takes a const reference (preferred if it's not changing the value).

[RoguelikeRazuka]

Allright here's the Cron algorithm itself:

1. Allocate the tasks among the processors randomly, thust getting an approximate solution

   1.1 Let j := 1, that is we're assigning task 1 to a random processor

   1.2 Generate a random integer in range [1..N], k := random(1, N)

   1.3 Assign task 1 to processor k

   1.4 Increment j := j + 1

   1.5 j > M? If it is so, go to Step 2 else repeat steps 1.1 - 1.5 

2. Improving the schedule we have got

   2.1 Calculate the loads on the processors

   2.2 Let p* be the processor which load is maximal (define it as T_max).
            Let p' be the processor which load is minimal (define it as T_min)
   
   2.3 Calculating delta := T_max - T_min

   2.4 Looking through the tasks on processor p*

   2.5 If we find a task which execution time is less than delta, assign it to
            processor p' (removing it from p*) and return to step 2.1, else go to step 2.6

   2.6 For each i (i := 1..k), for each j (j := 1..l):
       If tau(t_i) > tau(t_j) and tau(t_i) - tau(t_j) < delta, then swap t_i and t_j, return to 2.1

            (Where t_i is the i-th task assigned to p*, k tasks alltogether; t_j is the j-th task
            assigned to p', l tasks altogether)

   2.7 If no task reallocation has been done on step 2.6, then we conclude that the schedule
        can't be improved any further, go to step 3.

3. THE END

[Bumber]

You can't take a reference to a const variable, because a reference means changeable.

You can fix this a few ways: remove the const tag where it's being added, cast the const variable to the non-const type, or change the function so that it takes a const reference (preferred if it's not changing the value).

The problem is I'm not sure where it's being added. The compiler is complaining about the type of the class itself (this pointer.) Here's the relevant class with the unimportant stuff gutted:

Code: (C++) [Select]

  // Class for an entire scene, tying together all the other classes in this module.
  class Scene {
  private:
    //declaring a bunch of smart pointer vectors
  public:
    Scene(std::shared_ptr<Light> ambient_light, std::shared_ptr<Color> background_color, std::shared_ptr<Camera> camera, bool perspective) : //-constructor with initialization list-
    //-fill some vectors here-
    std::shared_ptr<Image> render(int width, int height) const { //this class's most important function
      //declare some more things
      //for loops
      compute_ray(x,y,image,origin,dir); // <-- problematic function call
      //more stuff
      return image;
    }
  private:
    void compute_ray(int x, int y, const std::shared_ptr<const Image> image, std::shared_ptr<Vector4> origin, std::shared_ptr<Vector4> dir) { //origin and dir will be modified
        double l = _camera->l(), b = _camera->b(), u, v; //_camera is a private variable of Scene; l() and b() are const functions
        std::shared_ptr<Vector4> right;
        u = l + (_camera->r() - l)*(x + 0.5)/(image->width()*1.0); //r() is also a const function
        v = b + (_camera->t() - b)*(y + 0.5)/(image->height()*1.0); //as is t()
        right = _camera->up->cross(-*dir); //up() is const, return type const Vector4&; cross(const Vector4& right) is const, returns Vector4 pointer
        *right = (*right)/right->magnitude(); //this is normalizing the vector
        if(_perspective) {
          dir = *(*(*-_camera->gaze()*(-_camera->d())) + (*right)*u) + _camera->up()*v //d() is const; gaze() is const, return type const Vector4&;
          *origin = _camera->location(); //location() is const, returns Vector4&
        }
        else {
          *dir = _camera->gaze();
          origin = *(_camera->location() + (*right)*u) + _camera->up()*v;
        }
        return;
    }
As far as I can tell, the error refers to the line "compute_ray(x,y,image,origin,dir);" which would implicitly be "this.compute_ray(x,y,image,origin,dir);"

I'd try removing const from the render function, but the instructor put that there. Does the function's const just mean it doesn't modify members of the class (i.e., other classes are fair game?) Maybe the solution is to put const on the compute_ray function, to assure it I'm still not touching the class? I'll try later tomorrow, but it sounds like the right answer.

Edit: Yes, that fixed it. Now I just need to figure out change my Vector4's into Matrix3x3's to cross multiply, then back again.

[cerapa]

Render is a const function, this means that it can't call compute_ray, because it isn't const.

[Reelya]

Ahh yeah, that would be the problem. A const function won't change the object, so it's an error to call a non-const function from that, since that could break the const-ness.

[cerapa]

So yeah, problems with "this" means you look at the code that's creating the object, not the class itself.

Code: [Select]

class someclass {
void constfunc() const {
nonconstfunc();
}

void nonconstfunc() {
;
}
};

error: passing 'const someclass' as 'this' argument of 'void someclass::nonconstfunc()' discards qualifiers [-fpermissive]

You are mistaken.

[Reelya]

But that is the code that's creating the reference (which is what we are having problems passing). I wasn't aware that it was called from code within the same class until just now however because I didn't have time to read all the code dump. But still, the point stands that you look at the code initiating the function call, rather than the callee.

[Spehss _]

Trying to make a program for a college class that writes data to a file from a structure, and can read data from the file to display on screen. Currently have two char pointers in the struct for use in dynamically made arrays. When reading the struct data from the binary file, the program crashes upon trying to print either array of chars. Presumably because it doesn't assign anything to the pointers when reading data from the file?

Can I not use pointers and dynamic memory for binary file input/output? O am I just doing something wrong?

[MagmaMcFry]

You're doing something wrong.

[Spehss _]

I'm not really sure what I'm doing wrong then. New to working with binary data files. The few examples I've worked on from my college textbook don't give many details on what's written to the binary file or read from the binary file. As far as I can see, it just writes data for a struct to a file, and when read from the file it copies all the data from the initial struct, which was stored in the file, to the new struct. The example programs do not use any pointers or dynamic arrays, though. That's something I thought would work the same way. Obviously not, since it's broken.

Only reason I'm using char arrays in the struct is because the instructions say to.

Spoiler: code. Primary point of interest is the displayRecords() function, where the crash is. (click to show/hide)

Code: [Select]

#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstring>

using namespace std;

struct Item{
char* descr; //pointer for dynamic memory allocation
int quantity;
double wholesale, retail;
char* date; //pointer for dynamic memory allocation

void setDescr(string); //for working with dynamic memory
void setDate(string); //for working with dynamic memory
~Item(); //deletes dynamic memeory
};

void Item::setDescr(string input)
{
if(descr!=0)
{
delete[] descr;
descr=0;
}
descr=new char[input.length()];
strcpy(descr,input.c_str());
}

void Item::setDate(string input)
{
if(date!=0)
{
delete[] date;
date=0;
}
date=new char[input.length()];
strcpy(date,input.c_str());
}

Item::~Item()
{
if(descr!=0)
{
delete[] descr;
descr=0;
}
if(date!=0)
{
delete[] date;
date=0;
}
}

void addRecords(const char filename[])
{
Item in;
string input="";
cout<<"\n-----------------------\n";
//get description
cout<<"Enter a description of this item: ";
cin.ignore(); //ignores whitespace in stream from earlier cin use from menu()
getline(cin, input);
in.setDescr(input);
//cout<<"\n"<<in.descr<<endl; //debug

//get quantity
cout<<"Enter item quantity: ";
cin>>in.quantity;
//cout<<"\nYou entered: "<<in.quantity<<endl; //debug

//get wholesale and retail prices
cout<<"Enter wholesale price of this item: ";
cin.ignore(); //ignore whitespace from prior input
cin>>in.wholesale;
//cout<<"\nYou entered: "<<in.wholesale<<endl; //debug

cout<<"Enter retail price of this item: ";
cin.ignore(); //ignore whitespace from prior input
cin>>in.retail;
//cout<<"\nYou entered: "<<in.retail<<endl; //debug

//get date
cout<<"Enter the current date: ";
cin.ignore(); //ignore any whitespace from previous input
getline(cin,input);
in.setDate(input);
//cout<<"\nDate added: "<<in.date<<endl; //debug

fstream file(filename, ios::out|ios::app|ios::binary);
file.write(reinterpret_cast<char*>(&in),sizeof(in));
file.close();
cout<<"\nRecord written to file."<<endl;
}

void displayRecords(const char filename[])
{
Item out;
fstream file(filename, ios::in|ios::binary);
file.read(reinterpret_cast<char *>(&out),sizeof(out));

cout<<setprecision(2)<<fixed
// <<"Description: "<<out.descr //program crashes here
<<"\nQuantity: "<<out.quantity //displays ok
<<"\nWholesale Price: $"<<out.wholesale //displays ok
<<"\nRetail Price: $"<<out.retail //displays ok
<<"\nDate added to file: "<<out.date<<endl; //program crashes at either this or at cout<<out.descr, which is commented out
}

void menu(const char filename[])
{
char input;
do
{
cout<<"\n---------------------------------\n"
<<"What would you like to do with "<<filename<<"?"
<<"\nA) Add new records to the file."
<<"\nB) Display one record currently on file."
<<"\nC) Change any record currently on file."
<<"\nD) Display all records currently on file."
<<"\nQ) Quit Program."
<<"\n>>";
cin>>input;
switch(input)
{
case 'a':
case 'A': addRecords(filename); break;

case 'd':
case 'D': displayRecords(filename); break;
}
}while(input!='q'&&input!='Q');
}

int main()
{
const char FILENAME[]={"inventory.dat"};
fstream file(FILENAME, ios::out|ios::in|ios::binary);
if(!file)
{
//if file doesn't exist, an empty file is created by opening a file in out mode
cout<<"Error. "<<FILENAME<<" does not exist. Created a blank file named "<<FILENAME<<endl;
file.open(FILENAME,ios::out|ios::binary);
file.close();
}
file.close();

menu(FILENAME);

return 0;
}