Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve Documentation about Memory Access Cost #239

Open
FloydZ opened this issue Feb 4, 2025 · 0 comments
Open

Improve Documentation about Memory Access Cost #239

FloydZ opened this issue Feb 4, 2025 · 0 comments

Comments

@FloydZ
Copy link
Collaborator

FloydZ commented Feb 4, 2025

Currently many people have the following mental model for memory access cost: T + \log(M) (log memory costs). But in reality it looks more like this:

    def _compute_estimate_time_complexity(self, params):
        """Computes time complexity in estimate mode and converts to bit complexity.
    
        Computes time complexity (in estimate mode) for given parameter set and converts to bit complexity
        and adds memory access costs if set.
        """
        temp_time_complexity = self._compute_time_complexity(params)
        if self.bit_complexities:
            temp_basic_operation_cost = self.problem.to_bitcomplexity_time(
                temp_time_complexity)

            if self._memory_access != 0:
                temp_memory_access_cost = temp_time_complexity
                temp_memory_access_cost += self.memory_access_cost(
                    self.memory_complexity())
                temp_time_complexity = log2(int(2 ** temp_basic_operation_cost)
                                            + int(2 ** temp_memory_access_cost))
            else:
                temp_time_complexity = temp_basic_operation_cost

        return temp_time_complexity
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant